tdpci.cpp

gistfile1.cpp

#include <cstring>
#include <algorithm>
using namespace std;
 
int dp[305][305];
int dp2[305][305];
char str[305];
 
int f(int s, int e){
    if(s > e) return 0;
    if(~dp[s][e]) return dp[s][e];
    int ret = -1e9;
    for (int i=s; i<e; i++) {
        ret = max(ret,f(s,i) + f(i+1,e));
    }
    if(str[s] == 'i' && str[e] == 'i'){
        for (int i=s+1; i<e; i++) {
            if(str[i] == 'w'){
                ret = max(ret,f(s+1,i-1) + f(i+1,e-1) + 1);
            }
        }
    }
    return dp[s][e] = ret;
}
 
int g(int s, int e){
    if(s > e) return 0;
    if(~dp2[s][e]) return dp2[s][e];
    int ret = max(g(s+1,e),g(s,e-1));
    for (int i=s; i<e; i++) {
        ret = max(ret,g(s,i) + g(i+1,e));
    }
    if(str[s] == 'i' && str[e] == 'i'){
        for (int i=s+1; i<e; i++) {
            if(str[i] == 'w'){
                ret = max(ret,f(s+1,i-1) + f(i+1,e-1) + 1);
            }
        }
    }
    return dp2[s][e] = ret;
}
 
int main(){
    scanf("%s",str);
    memset(dp,-1,sizeof(dp));
    memset(dp2,-1,sizeof(dp2));
    int l = (int)(strlen(str));
    printf("%d\n",g(0,l-1));
}