题意 : 有两颗苹果树，在 1~T 的时间内会有两颗中的其中一颗落下一颗苹果，一头奶牛想要获取最多的苹果，但是它能够在树间转移的次数为 W 且奶牛一开始是在第一颗树下，请编程算出最多的奶牛获得的苹果数
分析 : 这题是不可能爆搜的，可组合的情况实在太多.......
定义 dp[ i ][ j ] ==> 在第 i 个时间点下已经转移了 j 次的最多苹果数是多少
根据定义和奶牛一开始在一号树这个条件，所以初始化时有两种情况
如果第一个时间点落下苹果的是一号树则初始化 dp[ 1 ][ 0 ] = 1、dp[ 1 ][ 1 ] = 0
否则的话就是 dp[ 1 ][ 0 ] = 0、dp[ 1 ][ 1 ] = 1
那么对于一个状态 dp[ i ][ j ] 而言，它能从什么状态转移而来？
其实能从前一个时刻是否选择转到or继续待在当前所处的这颗树
即 dp[ i ][ j ] = max( dp[ i-1 ][ j ] , dp[ i-1 ][ j-1 ] )
然后根据当前时间点哪颗树掉落了苹果决定是否给当前 dp[ i ][ j ] 进行+1操作( j 的奇偶决定了牛在哪颗树 )
其实如果爆搜的话可以根据每一次选or不选去另一颗树的方法来搜，最后会搜出一个二叉的递归树
而上述DP就是记录了搜索出来的搜索树节点的最优值，我是这样理解的.......
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; int dp[maxn][33]; int arr[maxn]; int main(void) { int T, W; while(~scanf("%d %d", &T, &W)){ for(int i=1; i<=T; i++) scanf("%d", &arr[i]); if(arr[1] == 1){ dp[1][0] = 1; dp[1][1] = 0; }else{ dp[1][0] = 0; dp[1][1] = 1; } int ans = 0; for(int i=2; i<=T; i++){ for(int j=0; j<=W; j++){ if(j > i-1) continue; /// 最多转 i - 1 次，所以 j 超过了则说明不合法了 if(j==0) dp[i][j] = dp[i-1][j] + (arr[i]==1); else{ dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); if(arr[i]==2 && (j&1)) dp[i][j]++; else if(arr[i]==1 && !(j&1)) dp[i][j]++; } if(i==T) ans = max(dp[i][j], ans); } } printf("%d ", ans); } return 0; }