Divisionn=1のとき明らかにNOよってn>=2とする。挿入は考えずに配列を前の部分(S)と後の部分(T)に分けてみる。S,Tは空であってもよいとする。w=Σ[y∈T](y)とする。SouvenirsDPエディトリアル見て書いたコード。2のsouvenirだけを使ったとき、重さの和がiとする。このときdp[i]=(x,y,z)は以下の意味。yは重さ1のsouvenirをいくつ使ったか。DP上図は3番目の入力例の文字列t="abcab"にダミーの1文字を加えたt+'#'="abcab#"に対してKMP法のDFAを描いたもの。!はその他の文字を表す。tはオーバーラップしてもよいので、最終状態からの遷移もほしい。そこで、末尾にダミーの文字を加えた。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。