TDPC I - iwi

問題リンク
atcoder.jp

iとwからなる文字列sが与えられる. s中の連続部分列が"iwi"となっているとき文字から削除できる（削除した後は左の文字列と右の文字列がマージされる）.
このとき削除操作の最大回数を求める.

考察
dp[i][j] := [i,j)内で削除した文字数の最大値として区間dpをする.
いま, [i, j)を見ているとき, s[i] = 'i', s[j-1] = 'i'である区間についてs[k] = 'w'であるようなkが存在し, なおかつkによって分割できる区間[i,k), [k, j)について併合可能か見る

これを区間幅の小さい方から行っていくと解ける.
操作回数を求めるとあるが, 消去した文字数を3で割れば操作回数がわかる.

int dp[310][310];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  string s; cin >> s;
  int n = s.size();

  for(int i=3; i<=n; i++){
    for(int j=0; j<n; j++){
      if(i+j > n) break;
      int l = j, r = i+j; // [l,r)
      
      if(s[l] == 'i' && s[r-1] == 'i') {

        for(int k=l+1; k<r-1; k++){
          if(s[k] == 'w'){
            // [l, k) [k, r)

            if(dp[l+1][k] == k-l-1 && dp[k][r-1] == r-1-k-1){
              dp[l][r] = r-l;
            }
          }
        }
      }
      for(int k=l+1; k<r; k++){
        dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r]);
      }
    }
  }
  cout << dp[0][n]/3 << endl;
  return 0;
}