TopCoder SRM 576 Div1 Medium TheExperiment

問題

n個の水滴滴下装置が直線上に並んでいる。
i番目の装置は0.5 + iメートルのところに設置されていて、毎秒intensity[i]滴の水滴を落とす。

ここに長さLメートルのスポンジをM枚おいて、スポンジに水滴をたらす。
スポンジは左端をちょうどxメートル（xは0以上の整数）の場所にしかおけない。
スポンジはそれぞれ異なる高さに置く。

スポンジは、自分が一番上にある区間に含まれる装置の水滴を全部吸収する。
全てのスポンジが吸収する水滴の量は毎秒A以上B以下でなければならない。

スポンジの置き方は何通りあるか。
ただし、それぞれのスポンジが何番目の装置の水滴を吸収するかだけを区別する。
また、スポンジに区別はないものとする。

制約条件

n≦300
1≦intensity[i]≦9

方針

スポンジを左から置いていくDP.
dp[何メートルまでカバーしたか][何枚スポンジを使ったか][状態] := 場合の数
を更新する。

dp[i][j][k]で、状態kは、
0 : ちょうどiの位置にスポンジが存在しない状態
1 : iの位置をスポンジで覆わなければならない状態
2 : iの位置にはスポンジの右端があり、次にその下にスポンジを潜らせられる状態。

これで次に置くスポンジに何個分の装置を担当させるかで遷移させる。
時間計算量O(nML), 空間計算量O(nM)

ソースコード

class TheExperiment {
	public:
	
	static const int mod = (int)1e9 + 9;
	int dp[310][310][3];
	
	int countPlacements(vector <string> intensity, int M, int L, int A, int B) {
		memset(dp, 0, sizeof(dp));
		
		vi num;
		{
			string s;
			rep(i, intensity.size()) s += intensity[i];
			rep(i, s.size()) num.pb(s[i] - '0');
		}
		int n = num.size();
		dp[0][0][0] = 1;
		
		rep(i, n) rep(j, M) rep(f, 3) if(dp[i][j][f]){
			
			int sum = 0;
			rep(k, L) if(i + k < n){//k+1個分担当させる
				sum += num[i + k];
				int nf;
				if(f <= 1) nf = k == L - 1 ? 2 : 1;
				if(f == 2) nf = 2;
				
				if(A <= sum && sum <= B)
					(dp[i + k + 1][j + 1][nf] += dp[i][j][f]) %= mod;
			}
			if(f != 1) (dp[i + 1][j][0] += dp[i][j][f]) %= mod;//置かない
		}
		
		ll ans = 0;
		rep(i, n + 1) ans += dp[i][M][2];
		return ans % mod;
	}
};