[CQOI2007]涂色

题目

潮考我的题，之后我就给秒了

显然这个数据范围很是区间(dp)，我们设(dp[i][j])表示把区间([i,j])染成目标颜色的最小花费

首先初始化显然(dp[i][i]=1)

区间(dp)的常规套路显然，枚举断点(ileq k<j)，(dp[i][j]=min(dp[i][k]+dp[k+1][j]))

观察这个题的一个性质，如果(S[i]=S[j])，那么那么(dp[i][j])这个状态可以直接继承(dp[i+1][j])或(dp[i][j-1])，我们可以视为出示涂的时候直接把([i,j])这段都涂了，这样涂这个新格子的花费就算在最开始的初始化里了

代码

#include<cstdio>
#include<cstring>
#define re register
#define min(a,b) ((a)<(b)?(a):(b))
int n,dp[55][55];
char S[55];
int main() {
	scanf("%s",S+1);n=strlen(S+1);
	memset(dp,20,sizeof(dp));
	for(re int i=1;i<=n;i++) dp[i][i]=1;
	for(re int p=2;p<=n;p++) 
		for(re int i=1;i+p-1<=n;i++) {
			re int j=i+p-1;
			if(S[i]==S[j]) {
				dp[i][j]=min(dp[i+1][j],dp[i][j]);
				dp[i][j]=min(dp[i][j-1],dp[i][j]);
			}
			for(re int k=i;k<j;k++) 
				dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);
		}
	printf("%d
",dp[1][n]);
	return 0;
}