Atcoder Educational DP Contest M Candies を解く（解けなかった）

CS6.006で習ったことだし、DPに強くなりたい。

問題は以下。 atcoder.jp

1. 状態遷移図を書く。

   

   遷移図

2. 一つのノードから分岐する全てのノードを網羅できるようなサブ問題を考える。 ここでは、根ノードとそこからわかれる二つのノードを網羅する例を考えている。

3.境界条件も考える。

4.定式化する。

5.普通は漸化式ができれば万歳なのだが、今回はO(NK²)で間に合わないので、式を簡略化する。

アとア'、ウとウ’は同じなので、以下のように簡略化できる。

6.for文の回し方を考える。

iは大きい方から小さい方向(Nから0) kは小さい方から大きい方向(0からK)へ回す必要がある。

実際に書いたコードがこれ。 サンプルケースは全て通るが、ジャッジに通らない。よくわからないので保留。

#include "bits/stdc++.h"
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    int a[101];
    rep(i, 0, N) cin >> a[i];
    int** dp = new int*[102];
    rep(i, 0, 102){
        dp[i] = new int[100001];
    }
    rep(k, 1, 100001) dp[N][k] = 0;
    rep(i, 0, 102) dp[i][0] = 1;

    for(int k=0; k<=K; k++){
        for(int i=N; i>=0; i--){
            if(k - a[i] < 0){
                dp[i][k+1] = (dp[i][k] + dp[i+1][k+1]) % MOD;
            } else{
                dp[i][k+1] = (dp[i][k] + dp[i+1][k+1] - dp[i+1][k-a[i]])%MOD;
            }
        }
    }

    cout << dp[0][K] << endl;
    rep(i, 0, 102) delete[] dp[i];
    delete[] dp;
    return 0;
}