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; }