[CQOI2007]涂色

[CQOI2007]涂色

题目大意：

假设你有一条长度为(n)的木版，初始时没有涂过任何颜色。每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。问达到给定的目标至少要多少次操作？

思路：

(f[l][r])表示区间([l,r])至少要多少次操作。

转移分为两种：

1. (s_l=s_r)时，(f[l][r]=min(f[l][r-1],f[l+1][r]))；
2. (s_l eq s_r)时，(f[l,r]=min_{lle kle r}{f[l][k]+f[k+1][r]})。

时间复杂度(mathcal O(n^3))。

源代码：

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
const int N=51;
int s[N],f[N][N];
char str[N];
inline int getval(const char &ch) {
	return ch-'A';
}
int dp(int l,int r) {
	if(l==r) return 1;
	int &ret=f[l][r];
	if(ret) return ret;
	if(s[l]==s[r]) {
		return ret=std::min(dp(l,r-1),dp(l+1,r));
	}
	ret=INT_MAX;
	for(register int i=l;i<r;i++) {
		ret=std::min(ret,dp(l,i)+dp(i+1,r));
	}
	return ret;
}
int main() {
	scanf("%s",str);
	const int n=strlen(str);
	for(register int i=1;i<=n;i++) {
		s[i]=getval(str[i-1]);
	}
	printf("%d
",dp(1,n));
	return 0;
}