昨年のだるま落とし、ちらっと解説読みながらだけど AC できた。ちょっと嬉しい。
— つたじろう (ABC-D 29/43) (@_TTJR_) March 6, 2017
昨年歯が立たなかっただけに解けてうれしい。
問題概要
原文を参照してください → Daruma Otoshi | Aizu Online Judge
解説
take[i][j] := 区間 [i, j] のブロックを全て取ることができるか
となる bool 型の配列を用意します。まずはこの take
配列に対して、真偽値を正しく入れていきます。
条件より、区間の長さが であるときの判定は容易です。問題はその後でしょう。
次の つの事項を確認することによって、より長い区間についても判定できるようになります。
- 区間 のブロックを全て取ることができ、かつ 番目と 番目のブロックの重さの差が 以下であれば、区間 のブロックを全て取ることができる
- 区間 と 区間 について、両区間に対して全て取ることができるならば、区間 のブロックを全て取ることができる
したがって、以下のようにすれば take
配列を正しく構築できます。
この配列を元に答えを出すのですが、これに答えるには以下の補題を解かなければなりません。
の中に、長さが 以下の区間がたくさんある。その中から、区間どうしが同じ頂点を被覆しないようにいくつかの区間を選ぶときの、被覆できる頂点数の最大値を求めよ。
これは DP で解くことができます。
dp[i][j] := 区間 [i, j] において被覆できる頂点数の最大値
となるような配列 dp
を用意します。
この配列の初期化は各区間を見ることによって行います。例えば 長さ の区間 があったとします。 において被覆できる頂点数の最大値は当然 なので、dp[a][b] = M
が成り立ちます。これを全区間に対して行うことで初期化します。
あとは dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])
と更新してあげることで正答が得られます (発想としては前述の「より長い区間に対しても判定できる」の箇条書きの つめと一緒です)、 パワーを信じましょう。答えになるのは dp[0][N-1]
です。
ソースコード
bool take[310][310]; int dp[310][310]; signed main() { int n; while(cin >> n, n) { int w[310]; rep(i,0,n) cin >> w[i]; memset(take, false, sizeof(take)); memset(dp, 0, sizeof(dp)); rep(i,0,n) { rep(j,0,n-i) { int len = i+1; int s = j, t = j+i; rep(k,s,t) { if(take[s][k] && take[k+1][t]) take[s][t] = true; } if(len == 2) { if(abs(w[s] - w[t]) < 2) { take[s][t] = true; } } if(take[s][t]) { int x = s-1, y = t+1; while(1) { if(x < 0 || x >= n || y < 0 || y >= n) break; if(abs(w[x] - w[y]) >= 2) break; take[x][y] = true; x--; y++; } } } } rep(i,0,n) rep(j,i+1,n) { if(take[i][j]) dp[i][j] = j-i+1; } rep(i,0,n) rep(j,i,n) rep(k,i,j) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]); } cout << dp[0][n-1] << endl; } return 0; }
当時は「DP を 回やる」みたいなことを呟いている人がたくさんいるのを見て、こんなんできるわけ無いだろうと思っていたけど、今見ると DP を 回やる気持ちが確かに分かる。