题目大意：
有两棵苹果树（编号1和2），每分钟其中一棵树将会落下一个苹果，而牛要在两棵树下来回跑去接掉下的苹果（因为它不吃掉在地下的苹果）。而这只牛很懒，它不会为了吃而不停地来回跑。这里假设在t分钟内，牛只愿意跑w次，问牛最多能吃几个苹果。默认牛最初在1号树下。
我的理解：
这是一个DP问题。首先应根据第一分钟的苹果落下情况，对tree数组赋初值。
DP状态方程 dp[i][j] = max( dp[i-1][j] + dp[i-1][j-1] )，意思就是在前i分钟来回跑了j次吃到的苹果的最大数目；
其中dp[i-1][j]代表着上一次没有移动，dp[i-1][j-1] 代表上一次移动了。
其中还要注意的是当此次移动刚好有苹果落下时要将dp[]i[j]++；
我的代码：
#include <iostream> #include <cstdio> #include <cstring> #define MAX_T 1005 #define MAX_W 50 using namespace std; int dp[MAX_T][MAX_W]; int t,w; int tree[MAX_T]; int main() { freopen("D:/OJ/挑战程序设计竞赛/CatchApple.txt","r",stdin); int ans; while(scanf("%d %d",&t,&w) != EOF){ memset(dp,0,sizeof(dp)); //cin>>t>>w; for(int i = 1;i<=t;i++){ cin>>tree[i]; } if(tree[1] == 1){ dp[1][0]=1; dp[1][1]=0; }else{ dp[1][0]=0; dp[1][1]=1; } for(int i = 2;i<=t;i++){ for(int j = 0;j<=w;j++){ if(j == 0){ dp[i][j] = dp[i-1][j]+tree[i]%2; continue; } dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]); if(j%2+1 == tree[i]){ dp[i][j]++; } } } } ans = dp[t][0]; for(int i = 0;i<=w;i++){ if(ans < dp[t][i]){ ans = dp[t][i]; } } cout<<ans<<endl; return 0; }
