Codeforces 466(#266 Div2 only) D. Increase Sequence

問題

長さnの数列a[i]が与えられる。
この数列に区間[L, R]に一様に1を足すという操作を何回でも行うことができる。
ただし、一度使ったLは二度とLとして使うことができず、一度使ったRは二度とRとして使うことができない。
（[1, 1]で操作をしたら、[1, 2]は無理。[1, 2][2, 3]はＯＫ）

全ての数をhにしたいとき、区間の選び方は何通りあるか、mod 10^9 + 7で求めよ。
区間を選ぶ順序は無視する。

制約条件

0≦a[i]≦2000
h≦2000
n≦2000
入力は整数

方針

DP.
dp[位置][今終わってない区間の個数] := 場合の数
を更新するDPをすればよい。

遷移の仕方は、新しく区間を始めるかどうか*今までの区間を一つ終了するかどうか。
終了する場合は、区間の選び方がj通りある。

計算量はO(n^2)と見せかけて、
区間の和がちょうどh - a[i]になってないといけないので、dp[i][j]のjはh - a[i]プラマイ1の3通りしかなくて、実はO(n^2)になっている。
n≦2000なので意味ないけど。

ソースコード

const int mod = inf + 7;
int n, h, a[2001];
int dp[2001][2001];

int main(){
	cin >> n >> h;
	rep(i, n) cin >> a[i], a[i] = h - a[i];
	
	dp[0][0] = 1;
	rep(i, n) rep(j, i + 1) if(dp[i][j]){
		
		rep(b, 2) rep(e, 2){
			
			int nj = j - e + b;
			if(j + b != a[i]) continue;
			(dp[i + 1][nj] += (ll)(e ? a[i] : 1) * dp[i][j] % mod) %= mod;
		}
	}
	cout << dp[n][0] << endl;
	
	return 0;
}