Typical DP Contest I : イウィ

問題リンク :
I: イウィ - Typical DP Contest | AtCoder

問題概要 : 最大iwi数

解法 :
メモ化再帰 => WA
区間DP => TLE
TLEを解消する方法が全く浮かばなかったので諦めてrngさんのコードを参考に解いた

dp[L][R] := 閉区間[L,R]までで得られるiwiの最大値
区間DPでよくやる、長さが小さい順に値を更新をする

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

string s;
int dp[301][301];

int main() {
  getline(cin,s);
  int n = s.size();
  REP(length,1,n+1) rep(sp,n-length+1) { // length : 区間の長さ, sp : 左から順に区間の値を更新
    int ep = sp + length - 1;
    REP(k,sp+1,ep) dp[sp][ep] = max(dp[sp][ep],dp[sp][k]+dp[k+1][ep]);
    if( s[sp] == 'i' && s[ep] == 'i' ) {
      REP(k,sp+1,ep) if( s[k] == 'w' ) {
        bool fail = false;
        int len = (k-1)-(sp+1)+1;
        if( len && !( len >= 3 && dp[sp+1][k-1] == len ) ) fail = true;
        len = (ep-1)-(k+1)+1;
        if( len && !( len >= 3 && dp[k+1][ep-1] == len ) ) fail = true;
        if( !fail ) {
          dp[sp][ep] = ep - sp + 1;
          break;
        }
      }
    }
  }
  cout << (int)(dp[0][n-1]/3) << endl;
  return 0;
}