CODE FESTIVAL 2014 Hard B - ぽよぽよ

ぽよ〜

問題

code-festival-2014-morning-hard.contest.atcoder.jp

解法

dp で解けます。

dp[n][x] = (n 番目の人が, もとの位置から x 以下だけずれた座標にいるような場合の数)
とすると, n 番目の人は, p[n]+x-1 以下の座標にいるか, p[n]+x の座標にいるかのどちらかです。前者は dp[n][x-1] でわかりますね。後者は, n-1 番目の人が p[n]+x-1 以下の座標にいれば良いです。このような場合の数は, dp[n-1][y] で求めることができるので, 上手いことやりましょう。

const int MAXN = 1022;
const ll MOD = 1e9+7;
ll p[MAXN], l[MAXN];
ll dp[MAXN][2*MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    p[0] = -1ll<<50;
    for (int i = 1; i <= n; i++) cin >> p[i] >> l[i];
    for (int i = MAXN; i < 2*MAXN; i++) dp[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (ll x = -l[i]; x <= l[i]; x++) {
            ll y = p[i] - p[i-1] + x - 1;
            dp[i][x+MAXN] = dp[i][x+MAXN-1];
            y = min<ll>(y, 1000);
            y = max<ll>(y, -1001);
            if (y > -1001) {
                (dp[i][x+MAXN] += dp[i-1][MAXN+y]) %= MOD;
            }
        }
        for (ll x = MAXN+l[i]+1; x < 2*MAXN; x++) dp[i][x] = dp[i][x-1];
    }
    cout << dp[n][2*MAXN-1] << endl;
    return 0;
}