题意：有树1 树2 会掉苹果，奶牛去捡，只能移动w次，开始的时候在树1 问最多可以捡多少个苹果？
思路： dp[i][j]表示i分钟移动j次捡到苹果的最大值
实例分析
0,1 1,2...说明 偶数在树1 奇数在树2
for (int i = 1; i <= n; i++)
{
scanf("%d", &t[i]);
t[i] -= 1;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= w; j++)
{
if (j % 2) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + t[i];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + !t[i];
}
这里有个小技巧，不是每次要求输入1 2 2 之类的数据，我们把它们都-1 然后就可以就比较好看了
解释一下两句dp语句
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) 表示上一次要么在树1 要么在树2的情况，但是我只需要它们两者之间的最大值
解决问题的代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int dp[1010][35]; int t[1010]; int main() { int n, w; scanf("%d%d", &n, &w); for (int i = 1; i <= n; i++) { scanf("%d", &t[i]); t[i] -= 1; } for (int i = 1; i <= n; i++) for (int j = 0; j <= w; j++) { if (j % 2) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + t[i]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + !t[i]; } printf("%d\n", dp[n][w]); }