题意：2棵苹果树在 T（1 <= T <= 1,000） 分钟内随机由某一棵苹果树掉下一个苹果，奶牛站在树1或者树2下等着接苹果（接到的苹果被牛吃了，牛不吃掉在地上的苹果），它最多愿意移动W（1 <= W <= 30）次（从一颗树移动到另一棵树），问它最多能吃到多少个苹果。默认奶牛开始在第一颗树下。
Sample Input
7 2
2
1
1
2
2
1
1
第一列输入的分别是T、W，接下来的n列表示第 i 秒树（1或2）将掉下苹果。
Sample Output
6
Hint
INPUT DETAILS:
Seven apples fall - one from tree 2, then two in a row from tree 1, then two in a row from tree 2, then two in a row from tree 1. Bessie is willing to walk from one tree to the other twice.
OUTPUT DETAILS:
Bessie can catch six apples by staying under tree 1 until the first two have dropped, then moving to tree 2 for the next two, then returning back to tree 1 for the final two.
思路：
由题意可以定义dp[i][j]：在第 i 秒时，移动 j 次牛接到的最大的苹果数量。
因为牛一开始在树1下，所以可以得到如下的对应关系：
由图可以得到规律：当移动次数与牛所在的树的奇偶性不同时，牛可以接到这棵树这时掉下的苹果。
状态转移方程：
j = 0 时：dp[i][0] = dp[i - 1][0] + (arr[i] & 1);//没有移动说明一直在树1下。
j != 0) 时：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + ( (j & 1) != (arr[i] & 1) );
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 1000 + 5;
int arr[MAX_N];
int dp[MAX_N][35];
void solve(int t, int w) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= t; ++i)
for (int j = 0; j <= min(i, w); ++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]) + ((j & 1) != (arr[i] & 1));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t, w;
while (cin >> t >> w) {
for (int i = 1; i <= t; ++i)
cin >> arr[i];
solve(t, w);
cout << dp[t][w] << endl;
}
return 0;
}
