Codeforces #266 Div2 D. Increase Sequence

結構迷ったけど、何とか解けた。
http://codeforces.com/contest/466/problem/D

問題

数列A[i]が与えられるので、この値をすべてHにそろえたい。
数列の数値の変更方法として、数列の区間A[l]～A[r]をインクリメントすることができる。

ただし、複数の区間について上記インクリメントを行う場合、各要素は1回だけ左端にしかなれず、右端にも1回しかなれない。
区間の取り方は何通りあるか。

解法

各要素で端から、「この要素が何個分の区間の中にあるか」に対する組み合わせ数を保持してDPする。
各要素では、区間の始点になる・ならないおよび区間の終端になる・ならないの４通りの組み合わせを取れる。
また、区間の終端では、どの始点と対応付けれるかによって、始点の数分だけ組み合わせが取れる。

一見O(N^2)とかO(NH)に見えるけど、実際はO(N)。

int N,H,A[2001];
ll mo=1000000007;
ll dp[2001][2001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]>H) return _P("0\n");
		A[i]=H-A[i];
	}
	dp[0][0]=1;
	FOR(x,N) {
		
		dp[x+1][A[x]] += dp[x][A[x]];
		if(A[x]>=1) {
			dp[x+1][A[x]] +=  dp[x][A[x]-1];
			dp[x+1][A[x]-1] = A[x]*(dp[x][A[x]]+dp[x][A[x]-1])%mo;
		}
		dp[x+1][A[x]] %= mo;
	}
	cout << dp[N][0] << endl;
}

まとめ

本番結構迷ったけど、最終的に解けて良かった。