题解 | #[CQOI2007]涂色PAINT#
[CQOI2007]涂色PAINT
http://www.nowcoder.com/practice/512619bee5874e85bd2812a0c9066125
考虑区间,设表示将区间染色需要的最少染色次数, 然后我们考虑如何将区间合并,由于我们对于一段连续的区间可以在一次内涂完, 这就意味着如果我们就可以直接从和位置的答案里转移过来。 否者,我们就要枚举断点,将区间分为两部分染色,并将两部分的结果相加,取最小的。 具体转移方程如下:
#include <stdio.h>
int main()
{
char s[51];
int dp[51][51]={[0 ... 50]={[0 ... 50]=100}};
gets(s);
int len = strlen(s);
for(int length=1;length<=len;++length)
{
for(int l=0;l<len;++l)
{
int r = l+length-1;
if(r > len)
break;
if(l == r)
{
dp[l][r]=1;
continue;
}
if(s[l] == s[r])
dp[l][r] = dp[l+1][r] < dp[l][r-1] ? dp[l+1][r] : dp[l][r-1];
else
for(int k=l;k<r;++k)
dp[l][r] = (dp[l][k]+dp[k+1][r]) < dp[l][r] ? (dp[l][k]+dp[k+1][r]) : dp[l][r];
}
}
printf("%d",dp[0][len-1]);
return 0;
}