Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2009-day4 Chopsticks

問題文 : 塗り箸

解法 :
dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とすると

dp[i][i] = 1,
dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])

となる. これは, 区間の幅を小さいものから計算すれば実現できる.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	char str[512];
	unsigned int dp[512][512];
	
	scanf("%d", &n);
	scanf("%s", &str[1]);
	
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			dp[i][j] = 0xdeadbeef;
		}
		dp[i][i] = 1;
	}
	
	for (int d = 1; d < n; d++){
		for (int x = 1; x + d <= n; x++){
			for (int mid = x; mid <= x + d; mid++){
				dp[x][x + d] = min(dp[x][x + d], dp[x][mid] + dp[mid + 1][x + d]);
			}
			if (str[x] == str[x + d]) dp[x][x + d]--;
		}
	}
	
	printf("%u\n", dp[1][n]);
}