poj2358(递推 + dp)

题意：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下，所以可以得到如下的对应关系：

Paste_Image.png

由图可以得到规律：当移动次数与牛所在的树的奇偶性不同时，牛可以接到这棵树这时掉下的苹果。

状态转移方程：
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;
}