题目链接

Apple Catching POJ - 2385

思路

$$ dp[j] 表示移动i次时的最大值，一共t轮更新\\\\dp[j] = max(dp[j], dp[j - 1]) + (x \% 2 \ne j\%2) \\\\(x \% 2 \ne j\%2) 是根据题目中苹果下落位置与移动次数的奇偶性所得规律。 $$

时间复杂度

$$ O(TW) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 50;

int dp[MAXN];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);// don't forget &
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);// don't forget &
        for (int j = m; j >= 0; j--) {
            if (j == 0) {
                if (x == 1) {
                    dp[j]++;
                }
            } else {
                dp[j] = max(dp[j - 1], dp[j]);
                if (x % 2 != j % 2) {
                    dp[j]++;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= m; i++) {
        ans = max(ans, dp[i]);
    }
    printf("%d", ans);
    return 0;
}