問題文
参考にした解説
http://tsutaj.hatenablog.com/entry/2017/03/07/173127
https://kimiyuki.net/writeup/algo/etc/icpc-2016-domestic-d/
講評
https://icpc.iisf.or.jp/2016-tsukuba/review-by-chief-judge/?lang=ja
解説
下図のようにブロックが並べられているとする。
何もブロックを叩いていない状態では、「隣り合うブロックの重さの差が1以下」となる、①と②の二通りのブロックの落とし方がある。
①の叩き方を採用すると、区間$[0, 2)$はすべて叩き落とせる。
②の叩き方を採用すると、区間$[1, 3)$はすべて叩き落とせ、さらに、区間$[1, 3)$の両隣りのインデックス0のブロックとインデックス3のブロックも落とせて、合わせると区間$[0, 4)$のすべての区間を叩き落とせる。
このように、「連続してブロックを叩き落とせる区間」について、長さが2の区間から調べ、それより長い区間については前の計算結果を利用しながら調べていく。
以上から、すべての「連続してブロックを叩き落とせる区間」を調べると、下図の①～③ようになる。
列挙した①～③の区間のいくつかを選んで、最終的に落とせるブロックの数を求める。
区間①を選んだら、その区間とブロックを共有する区間②と区間③は選べない（なぜなら、区間$[0,1)$のブロックを崩した後はインデックス0と1のブロックは無くなってしまうから）。
区間②を選んだら、その区間とブロックを共有する区間①と区間③は選べない。
区間③を選んだら、その区間とブロックを共有する区間①と区間②は選べない。
よって、選べる区間の組み合わせは、区間①, 区間②, 区間③の内のどれかとなり、この内最もブロックを叩き落とせる区間③を選ぶのが正解となる。
以上から、「区間同士が同じ頂点（ブロック）を被覆（共有）しないようにいくつかの区間を選ぶときの、被覆できる最大の頂点の数」を求めれば、それが答えとなることがわかる。
自分の解答
- 「連続して取り出せる区間」を全列挙する
- 長さが2の区間から順に、より長い区間を求めていく。
- 長さ2の区間は「お互いのブロックの重さが1以下」
- それより長い区間$[l, r)$の区間が取り出せるのは、
- 区間$[l+1, r-1)$が取り出せて、なおかつ「インデックス$l$と$(r-1)$のブロックの重さの差が1以下の時
- 区間$[l, k)$と$[k,r)$が両方取り出せるような、$k$$(l < k < r)$が存在する時
- 以上の計算結果を、
isOK[l][r] := [l, r)のブロックが連続して取り出せるかとなるbool型の配列に保存
- 「連続して取り出せる区間」から、お互い同じ頂点を共有しない区間を選んだ時の、被覆する頂点数の最大値を求める。
- 「$DP[l][r] :=$ 区間$[l, r)$で取り出せる頂点の数の最大数」として、
- （初期化）
isOK[l][r] == trueなら、DP[l][r] = r - l - （遷移)
DP[l][r] = max(DP[l][r], DP[l][k] + DP[k][r]) (l <= k <= r) - で、計算結果の
DP[0][n]が答え - 具体的な遷移は以下の通り
for(int len = 0; len <= n; ++len) { // 短い長さの区間から遷移していく。
for(int left = 0; left <= n; ++left) {
int right = left + len;
if(n < right) break;
for(int k = left; k <= right; ++k) {
DP[left][right] = max(DP[left][right], DP[left][k] + DP[k][right]);
}
}
}
計算量は、1.と2.でそれぞれ$O(n^3)$で、合わせて$O(n^3)$。
$n$は300以下だから大丈夫そう？。
提出コード https://onlinejudge.u-aizu.ac.jp/status/users/misosiru65/submissions/1/1611/judge/4414173/C++14
「区間DP」とよばれる方法だそうです。
謎に感じているところ
最後の区間DPの遷移なんですが、
for(int left = 0; left <= n; ++left) {
for(int right = left; right <= n; ++right) {
for(int k = left; k <= right; ++k) {
DP[left][right] = max(DP[left][right], DP[left][k] + DP[k][right]);
}
}
}
と書いてもAcceptedになってしまいました。で、最後の答えとしてleft == 0の部分しか参照しないので、無駄を省いた以下の遷移でもAcceptedになりました。
for(int right = 0; right <= n; ++right) {
for(int k = 0; k <= right; ++k) {
DP[0][right] = max(DP[0][right], DP[0][k] + DP[k][right]);
}
}
なぜこの遷移の順序で正しい答えがでるのか、その根拠がいまいちわかっておらず、説明もできない次第です。多分、ワーシャルフロイド法みたいな見た目をしているので、それがヒントになりそうだなと思っていますが、わかる人や、手掛かりとなる資料など知っている人いたらコメントで教えてほしいです。
(多分、区間を一つずつ伸ばしていって、一つ短い区間での計算結果も反映して遷移するから、これで正しそうな気はする)
区間DPについての参考資料