[CQOI2007] 涂色

[CQOI2007] 涂色

题意

给出一个字符串，每个位置有一种颜色。

有一个初始无颜色的字符串，每次可以把一段字符染成同一种颜色。

求最少染多少次色，能把两个字符串变成一样。

思路

区间动态规划。

定义 \(dp_{i,j}\) 表示把 \([l,r]\) 这段区间染成一样需要的最小次数。

发现染色有两种方法：

1. AABBB 左右分开染色。
2. AABBAAA 先染成 A，再把中间染成 B。

对于第一种染色方法，转移方程即 \(dp_{i,j}=\min_{i\le k < j} dp_{i,k}+dp_{k+1,j}\)。

对于第二种染色方法，必须满足 \(S_i=S_j\)，转移方程 \(dp_{i,j}=\min dp_{i,j-1},dp_{i+1,j}\)。

就是染 \(j\) 时，把区间向左扩展到 \(i\) 再继续剩下的染色。

或者染 \(i\) 时，把区间向右扩展到 \(j\) 再继续剩下的染色。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
char S[N];
int dp[N][N], n;
int main() {
	scanf("%s", S + 1);
	n = strlen(S + 1);
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= n; i ++) dp[i][i] = 1;
	for (int len = 1; len <= n; len ++) {
		for (int i = 1; i <= n; i ++) {
			int j = i + len;
			if (j > n) break;
			if (S[i] == S[j]) 
				dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
			for (int k = i; k < j; k ++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
		}
	}
	cout << dp[1][n] << "\n";
	return 0;
}