Typical DP Contest I - イウィ

問題文 : イウィ

Greedy でも解けるらしいが, ここはDP.

$check[x][y] :=$ 区間x, y を適切な順番で取り除くことですべてをiwiとして取り出せるか？ とする.
あとは, 個数が最大になるように同じようにDP テーブルを更新していく. $O(N^3)$.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

using namespace std;

bool memo[333][333];
int dp[333][333];

int main()
{
	//memset(memo, -1, sizeof(memo));
	char s[1024];
	
	scanf("%s", s);
	int l = strlen(s);
	
	for (int i = 0; i < l; i++)
		for (int j = 0; j < i; j++)
			memo[i][j] = true;
	
	for (int d = 3; d <= l; d++){
		for (int i = 0; i <= l - d; i++){
			for (int j = i + 1; j < i + d - 1; j++){
				if (s[i] == 'i' && s[j] == 'w' && s[i + d - 1] == 'i' &&
					memo[i + 1][j - 1] && memo[j + 1][i + d - 2]) memo[i][i + d - 1] = true;
				if (memo[i][j] && memo[j + 1][i + d - 1]) memo[i][i + d - 1] = true;
			}
		}
	}
	
	for (int i = 0; i < l; i++)
		for (int j = i + 1; j < l; j++)
			if (memo[i][j]) dp[i][j] = (j - i + 1) / 3;
	
	for (int d = 3; d <= l; d++){
		for (int x = 0; x <= l - d; x++){
			dp[x][x + d] = max(dp[x][x + d], max(dp[x + 1][x + d], dp[x][x + d - 1]));
			for (int mid = x + 1; mid < x + d - 1; mid++){
				dp[x][x + d] = max(dp[x][x + d], dp[x][mid] + dp[mid + 1][x + d - 1]);
			}
		}
	}
	
	printf("%d\n", dp[0][l - 1]);
	
	return (0);
}