CF518 Div2 D - Array Without Local Maximums

これ割とあからさまなdpじゃない?

問題

いくつかの要素が-1になっている長さnの数列が与えられる
↓の条件を満たすように-1を1〜200に変えるとき、何通りの数列が作れるか
1) a[1] <= a[2]
2) a[n-1] >= a[n]
3) a[i] <= max(a[i-1], a[i+1]) (1 < i < n)

2 <= n <= 10^5

解法

dp[i][j][k]: i-1番目まで埋め終わってて、a[i-1]をjに変えて、a[i-1]とa[i-2]の関係がkであるような数列の個数
k=0) a[i-2] > a[i-1]
k=1) a[i-2] = a[i-1]
k=2) a[i-2] < a[i-1]

条件3よりk=0,1のときはa[i]は自由に決められる
k=2のときはa[i-1] <= a[i]となるようにしないといけない
よってdp[1][j][2]のみ1にしておけば条件1は勝手に満たせる
また条件2より答えは Σ dp[n][j][0,1]

遷移はa[i]≠-1のときは普通に
dp[i+1][a[i]][〜] += dp[i][j][k] (1 <= j <= 200)
そうじゃないときはまともにやると
dp[i+1][j'][〜] += dp[i][j][k] (1 <= j <= 200, 1 <= j' <= 200)
でTLEするけど、imos法を使えばj'のループが必要なくなる

実装

メモリ制限は512mbだから節約しなくても足りる

int n, a[100100], dp[100100][222][3];

signed main() {
	cin >> n;
	rep(i,n) cin >> a[i];
	if (a[0]!=-1) dp[1][a[0]][2] = 1;
	else reps(i,1,201) dp[1][i][2] = 1;
	reps(i,1,n) {
		if (a[i]==-1) {
			reps(j,1,201) rep(k,3) {
				if (k!=2) {
					if (j>=2) (dp[i+1][1][0] += dp[i][j][k]) %= mod,
							  (dp[i+1][j][0] += mod-dp[i][j][k]) %= mod;
					(dp[i+1][j][1] += dp[i][j][k]) %= mod;
					if (j<=199) (dp[i+1][j+1][2] += dp[i][j][k]) %= mod;
				}
				else {
					(dp[i+1][j][1] += dp[i][j][k]) %= mod;
					if (j<=199) (dp[i+1][j+1][2] += dp[i][j][k]) %= mod;
				}
			}
			rep(k,3) if (k!=1) reps(j,1,201) (dp[i+1][j][k] += dp[i+1][j-1][k]) %= mod;
		} else {
			reps(j,1,201) rep(k,3) {
				if (k!=2) (dp[i+1][a[i]][a[i]==j ? 1 : (j<a[i] ? 2 : 0)] += dp[i][j][k]) %= mod;
				else if (j<=a[i]) (dp[i+1][a[i]][(a[i]==j ? 1 : 2)] += dp[i][j][k]) %= mod;
			}
		}
	}
	int res = 0;
	reps(i,1,201) rep(j,2) (res += dp[n][i][j]) %= mod;
	cout << res << endl;
}

http://codeforces.com/contest/1068/problem/D