BZOJ 1260 [CQOI2007]涂色paint

题目大意

给你一个目标序列，让你对一个空白序列染色，后染的会覆盖先染的，求使空白序列变为目标序列的最小染色次数。

这题看到区间操作求最优方案这种问题基本就断定是区间DP了。

设$F_{i,j}$为染区间[i,j]到对应目标状态的最小染色次数。之后考虑如何递推。

对于每一个区间[i,j]，需要考虑的是边界i,j是否相同。如果相同那么就说明不用染色，此时$F_{i,j} = \min(F_{i+1,j-1},F_{i+1,j},F_{i,j-1})$；如果不相同那么必须进行分别染色，此时枚举K，则有$F_{i,j} = \min (F_{i,k} + F_{k+1,j})$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,f[51][51];
char s[51];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;++i) f[i][i]=1;
    for(int k=1;k<=n;++k)
        for(int i=1;i+k<=n;++i)
        {
            if(s[i]==s[i+k]) f[i][i+k]=min(f[i+1][i+k-1]+1,min(f[i][i+k-1],f[i+1][i+k]));
            else for(int j=0;j<k;++j) f[i][i+k]=min(f[i][i+k],f[i][i+j]+f[i+j+1][i+k]);
        }
    printf("%d\n",f[1][n]);
    return 0;
}