Suikaba https://blog.hatena.ne.jp/Suikaba/ すいバカ日誌 https://suikaba.hatenablog.com/ 競プロ AtCoder TDPC 問題文 http://tdpc.contest.atcoder.jp/tasks/tdpc_concatenation 解法 同じ文字列を複数選んでも良いので，何を使ったかを保存する必要はないです． 今作っている文字列の状態がどうか，がわかれば十分．そこで突然ですが，以下のような dp をします． dp[i][j][k] := 文字列が i 文字目まで出来ているとき，直近 7 文字が j で，単語の区切り位置としてありえるのが k であるような場合の数この DP において，今できている文字列から次の新しい文字列を作る時，単語単位で追加していくのではなく，文字単位(0 or 1)で追加していくと… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsuikaba.hatenablog.com%2Fentry%2F2017%2F08%2F27%2F181249" title="Typical DP Contest Q - 連結 - すいバカ日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-08-27 18:12:49 rich https://suikaba.hatenablog.com/entry/2017/08/27/181249 1.0 100%