Codeforces #346 Div2. G. Fence Divercity

解けて良かった。
http://codeforces.com/contest/659/problem/G

問題

1辺1の正方形を綺麗に縦に積んだものをボードと呼ぶ。
N個のボードが横1列に並んでおり、それぞれ高さはH[i]である。

これらのボード群のうち、以下のような正方形の取り除き方は何通りあるか。

• 各ボードに対し、正方形を取り除く場合は上からいくつかを取り除く。
• 取り除いた正方形群は連結する。
• 各ボードは最低1の高さは残すこと。

解法

ボードが左から右に順に並んでいるとする。
DPで各ボードが取り除く右端である場合の取り除き方の組み合わせを求め、その和を取ろう。
最初にH[i]をデクリメントしておくとよい。

i番目のボードを取り除く右端とする場合、以下の2値を考える。

• i列を取り除く右端とする組み合わせのうち、i列の取り除く個数が(i+1)列と連結しうる数だけ取り除く場合。(H[i]≦H[i+1]またはH[i]＞H[i+1]だけど、i列を(H[i]-H[i+1])個を超えて取り除く場合)
• i列を取り除く右端とする組み合わせのうち、i列の取り除く個数が(i+1)列と連結しえない数だけ取り除く場合。(H[i]＞H[i+1]かつi列を取り除く数が(H[i]-H[i+1])以下の場合)

i列の両隣H[i-1],H[i],H[i+1]の大小関係を見て、丁寧に上記2値を更新していこう。

int N;
int H[1010010];
ll mo=1000000007;
ll dp[1010100][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	for(i=1;i<=N;i++) cin>>H[i], H[i]--;
	
	for(i=1;i<=N;i++) {
		if(H[i-1]<=H[i]) {
			if(H[i]<=H[i+1]) {
				dp[i][0]=(H[i]+dp[i-1][0]*H[i-1])%mo;
			}
			else {
				if(H[i-1]<=H[i+1]) {
					dp[i][0]=H[i]-H[i+1];
					dp[i][1]=(H[i+1]+H[i-1]*dp[i-1][0])%mo;
				}
				else {
					dp[i][0]=(H[i]-H[i+1]+(H[i-1]-H[i+1])*dp[i-1][0])%mo;
					dp[i][1]=H[i+1]*(1+dp[i-1][0])%mo;
				}
			}
		}
		else {
			if(H[i]<=H[i+1]) {
				dp[i][0]=(1+dp[i-1][1])*H[i]%mo;
			}
			else {
				dp[i][0]=(H[i]-H[i+1])*(1+dp[i-1][1])%mo;
				dp[i][1]=H[i+1]*(1+dp[i-1][1])%mo;
			}
		}
		(ret+=dp[i][0]+dp[i][1])%=mo;
	}
	cout<<ret<<endl;
	
}

まとめ

本番大小関係が混乱してだいぶ手こずった。