AOJ 2665 Hopping Hearts

問題概要

長さL-1の平均台の上にN羽のうさぎがいる。i番目のうさぎの初期位置はx_iであり、0 ≤ x_i ≤ x_i+1 ≤ L-1を満たす。

それぞれのうさぎは、1回ジャンプすると右にa_iだけ移動できる。任意の回数ジャンプすることできるが、別のうさぎを飛び越えたり、L以上の位置に移動することはできない。同時にジャンプしていられるのは高々 1 羽であり、ある位置に存在できるうさぎの数も高々 1 羽である。

初期状態から始めてジャンプを任意の回数繰り返したあとの状態として、あり得るものは何通りあるか。1 000 000 007 で割った余りで求めよ。

制約

• 1 ≤ N ≤ 5000
• 1 ≤ L ≤ 5000
• 0 ≤ x_i ≤ x_i+1 ≤ L-1
• 0 ≤ a_i ≤ L-1

解法

ごちうさを見ると解ける。

DPをする。
dp[i][j] := i番目のうさぎまで見て、区切り板がjにあるときの場合の数。
区切り板は越えることのできない壁を表す。

上記のdpだと5000 × 5000のメモリを消費するが、1つ前のうさぎの状態がわかれば良いので2 × 5000のメモリ量で済む。

注意点は、うさぎはその場でぴょんぴょんすることがあるということである。

コード

#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
const ll MOD = ((1e9) + 7);
  
int dp[2][5050];
  
int main()
{
    int N, L;
    scanf("%d %d", &N, &L);
    vector<int> x(N), a(N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &x[i]);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
  
    fill(dp[0], dp[0] + L, 1);    
    for (int i = 0; i < N; i++) {
        int curr = i & 1, next = !curr;
        for (int j = x[i]; j < L; j += a[i]) {
            if (j > 0) {
                dp[next][j] += dp[curr][j-1];
            } else {
                dp[next][j] = dp[curr][j];
            }
            dp[next][j] %= MOD;
            if (a[i] == 0) break;
        }
          
        for (int j = x[i]; j < L; j++) {
            dp[next][j+1] += dp[next][j];
            dp[next][j+1] %= MOD;
        }
        fill(dp[curr], dp[curr] + L, 0);
    }
    printf("%d\n", dp[N&1][L-1]);
    return 0;
}