Codeforces Round #303 (Div. 2) C. Woodcutters

Codeforces Round #303 (Div. 2)に参加。結果は全完で236位でした。全完出来たのは嬉しいけどB問題でわけのわからんつまり方して順位を大きく落としたのは残念。

問題

Problem - 545C - Codeforces

解法

貪欲で解けるらしいがメモ化再帰で解いた。
dp[n][flag] := n本目の木を見ている時これから先最高何本の木を倒すことができるか(flagが0なら前に倒すことが出来て,flagが1なら前に倒すことが出来ない)

と定義する。
flagが0の時は前に倒すほうが絶対に良いので前に倒して次に進む。
flagが1の時はn本目の木を後ろに倒すか倒さないかで場合分けして最大値を取る。

以下ソースコード

const int MAXN = 100010;
int dp[MAXN][2];
int x[MAXN], h[MAXN];
int n;

int dfs(int now, int emp) {
    if (now == n) return 0;
    if (now == n-1) return 1;
    int& ret = dp[now][emp];
    if (ret >= 0) return ret;
    ret = 0;
    if (emp == 0) {
        int nemp = 0;
        if (x[now+1]-h[now+1] > x[now]) nemp = 0;
        else nemp = 1;
        ret = dfs(now+1, nemp)+1;
    } else {
        {
            int nemp = 0;
            if (x[now+1]-h[now+1] > x[now]) nemp = 0;
            else nemp = 1;
            ret = dfs(now+1, nemp);
        }
        if (x[now]+h[now] < x[now+1]) {
            int nemp = 0;
            if (x[now+1]-h[now+1] > x[now] + h[now]) nemp = 0;
            else nemp = 1;
            ret = max(ret, dfs(now+1, nemp) + 1);
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> h[i];
    }
    x[n] = 1<<31;
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0) << endl;
    return 0;
}