Day9 - A - Apple Catching POJ

Description

有两棵APP树,编号为1,2.每一秒,这两棵APP树中的其中一棵会掉一个APP.每一秒,你可以选择在当前APP树下接APP,或者迅速移动到另外一棵APP树下接APP(移动时间可以忽略不计),但由于却乏锻炼,你最多移动W次.问在T秒内,你最多能收集多少个APP.假设你开始站在1号APP树下.

Input

第1行：两个整数T（1 < = T< = 1000）和W（1 < = W< = 30）
第2..T+1行：1或2，代表每分钟掉落APP的那棵树的编号

Output

一行一个整数，代表你移动不超过W次能接住的最大APP数

Sample Input

Sample Output

6

思路：简单的dp，设状态转移为dp[i][j],第i秒，移动了j次,能抓住的APP为dp[i][j],对于每次j，有两种状态：苹果在该位置，苹果不在该位置，若苹果在该位置，dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+1,若苹果不在该位置,dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])，再使用滚动数组压缩即可

int dp[];

int main() {

    ios::sync_with_stdio(false), cin.tie();

    int T, W, val;

    cin >> T >> W;

    for(int i = ; i <= T; ++i) {

        cin >> val;

        for(int j = W; j >= ; --j) {

            if((j+)% == (val%)) dp[j] = max(dp[j], dp[j-]) +;

            else dp[j] = max(dp[j], dp[j-]);

        }

    }

    int ans = ;

    for(int i = ; i <= W; ++i)

        ans = max(ans, dp[i]);

    cout << ans << "\n";

    return ;

}

巴特西

Day9 - A - Apple Catching POJ - 2385

最新文章

热门文章