emtubasa https://blog.hatena.ne.jp/emtubasa/ ツバサの備忘録 https://emtubasa.hateblo.jp/ 動的計画法(DP) 問題 解法 この解法はばたこ(@btk15049)さんから聞いたものになります。 dp[i] = i番目の単語までで、消去できる単語数の最大値 とします。 すると、i番目の単語を利用して、それより前の単語を消すかどうかの2パターンにまず分かれます。 i番目の単語を利用しない場合は、dp[i-1]になるので省略します。 i番目の単語を利用する場合、1~i-1番目の単語のなかからj番目を選んだときに、i番目とj番目の先頭の文字が同じ場合、j~i-1番目の単語が消去できます。 これはi-j個です。あとは1~j-1番目の消去数を最大にすればいいのですが、これはdp[j-1]を参照すれば求まります。 と… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femtubasa.hateblo.jp%2Fentry%2F2018%2F09%2F22%2F185003" title="AOJ 2892 - Aizu Competitive Programming Camp 2018 Day 3 D しりとり圧縮 (Shiritori Compressio - ツバサの備忘録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2018-09-22 18:50:03 rich https://emtubasa.hateblo.jp/entry/2018/09/22/185003 1.0 100%