Poj 2385: Apple Catching

poj2385.md

Poj 2385: Apple Catching

題目

分析

轉移方程式只想到前半段，後半段沒想到可以這麼做啊

###定義

Let dp[i][j] = 前 i 秒，最多 j 次轉換位置的情況下，可得到的最多蘋果。
答案 = dp[T-1][W]

###轉移方程式：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + (1 if 目前位置有降落蘋果 else 0)

其中目前位置可由

1. 起始位置是在 tree 1
2. 轉換位置的次數

得出：

current = (2 if j % 2 == 1 else 1)

###初使條件

dp[0][j] 看第一個掉落的是不是在 tree 1：

若是，則: dp[0][even] = 1; dp[0][odd] = 0;

若不是，則： dp[0][even] = 0; dp[0][odd] = 1;

另外，dp[i][0] 只可能從 dp[i-1][0] 來，且位置一定是在 tree 1。

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int T, W;
int data[1000];
int dp[1000][31];

int solve() {
    if (data[0] == 1) {
        dp[0][0] = 1;
        dp[0][1] = 0;
    }
    else {
        dp[0][0] = 0;
        dp[0][1] = 1;
    }
    for (int j = 2; j <= W; j++)
        dp[0][j] = dp[0][j-2];

    for (int i = 1; i < T; i++)
        dp[i][0] = dp[i-1][0] + ((data[i] == 1) ? 1 : 0);

    for (int i = 1; i < T; i++) {
        for (int j = 1; j <= W; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
            int current = ((j % 2 == 1) ? 2 : 1);
            if (current == data[i])
                dp[i][j]++;
        }
    }

    return dp[T-1][W];
}

int main() {
    scanf("%d %d", &T, &W);
    for (int i = 0; i < T; i++)
        scanf("%d", &data[i]);
    printf("%d\n", solve());

    return 0;
}