区間DPhttp://tdpc.contest.atcoder.jp/tasks/tdpc_iwi問題概要iとwの2種類の文字のみからなる文字列Sが与えられる。Sのある連続部分文字列が"iwi"となっているとき、その部分を取り除く操作を行うことができる。Sに対して最大何回この操作を行えるか求めよ。Sの連続部分文字列S[l..r]に対して行える最大操作回数とおく。区間の長さが3以下の場合は自明で、その区間に対応する部分文字列がiwiなら1でそれ以外なら0である。これら初期値をもとに区間を伸ばしながらDPを更新していく。更新は以下の2パターンを考えるとわかりやすいかもしれない。独立に消せる形iwiiwiのような形の文字列は左右のiwiを独立に消せる。ゆえにdpの更新では左の区間と右の区間の値を単純に足せばいい。iがくっついてそれも消せるようになる。重要なのはこうした連鎖が必ず「中が全部消せる→外にiwiが残ったのでそれも消せる」という流れで起きることである。ここで中が全部消せるかどうかはそれまでのdpの値を見ればわかる(例えば長さの6の区間のdp値が2ならその区間は全消しできる)。中の長さが区間の長さ-3になるような区切りを全部みてこういう形になっているかどうか判定すればよい。以上でO(N3)で答えが出る。長さNの01文字列Sが与えられる。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。