学步园

                                
想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
                                 
转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：有两个树，每分钟在某棵树的一颗会掉落一个苹果，奶牛可以在树下捡苹果，不过奶牛在两棵树之间的转移次数有限，所以问在t时刻，最大
转移次数为w，奶牛可以得到的最大苹果数，初始时奶牛在第一棵树

给出t与w
接着t行给出1,2分别代表那分钟是那棵树掉落了苹果

解题思路：每次奶牛只有两种决策，在某一分钟的时候转移或者不转移，我们只要知道前面分钟两者之间的最大值，继而可以得到当前状态的最大值
动态规划设dp[T][W]代表第T分钟的时候移动W次的所得到的最大苹果数
那么状态转移方程为:
dp[T][W] = max(dp[T-1][W] + (a[T]==W%2+1),dp[T-1][W-1]+(a[T]==W%2+1))
a[T]==W%2+1,是看当前转移了W次后在哪棵树下，当前能不能得到这个苹果

#include <stdio.h>
#include <string.h>
#define MAXT 1010
#define MAXW 35

int dp[MAXT][MAXW];
int a[MAXT];

int main(){
	int t,w,i,j;
	while(~scanf("%d%d",&t,&w)){
		dp[0][0] = 0;
		for(i = 1;i <= t;i++){
			scanf("%d",&a[i]);
			dp[i][0] = dp[i-1][0] + (a[i]==1);				//若不转移数为0，那么i时刻内得到的苹果是第一棵树掉落的苹果总数
		}
		for(i = 1;i<=w;i++)	dp[1][i] = 1;			//转移一次以上，那么第一分钟内的都可以得到1个苹果

		for(i = 2;i <= t;i++){
			for(j = 1;j <= w;j++){
				dp[i][j] = dp[i-1][j]+(a[i]==j%2+1);				//若在i分钟的时候转移到另一颗树上

				if(dp[i][j] < dp[i-1][j-1] + (a[i]==j%2+1)){		//若在i分钟的时候不转移到另一颗树上可以得到最大
					dp[i][j] = dp[i-1][j-1] + (a[i]==j%2+1);
				}
			}
		}
		printf("%d\n",dp[t][w]);
	}
	return 0;
}