有两棵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
7 2 2 1 1 2 2 1 1
output
6
还是太菜了，这题最后我看了题解，关键是要想到转移奇数次在2树下，转移奇数次在1树下，而至于他们选不选，是由编号与转移的次数共同决定的。
#include <iostream> #include <algorithm> #include <cstdio> int a[1003]; int dp[1002][44]; using namespace std; int main() { int t,w; cin>>t>>w; for(int i=1;i<=t;i++) { scanf("%d",&a[i]); a[i]--; } for(int i=1;i<=t;i++) { for(int j=0;j<=w;j++) { if(j%2!=0) { dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i]; } else { if(j) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+!a[i]; } else dp[i][j]=dp[i-1][j]+!a[i]; } } } cout<<dp[t][w]<<endl; }