P4170 [CQOI2007]涂色

· · 题解

题意是求对字符串的最少染色次数，设f[i][j]为字符串的子串s[i]~s[j]的最少染色次数，我们分析一下：

当i==j时，子串明显只需要涂色一次，于是f[i][j]=1。

当i!=j且s[i]==s[j]时，可以想到只需要在首次涂色时多涂一格即可，于是f[i][j]=min(f[i][j-1],f[i+1][j])

当i!=j且s[i]!=s[j]时，我们需要考虑将子串断成两部分来涂色，于是需要枚举子串的断点，设断点为k，那么f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])

总结一下就是：

f_{i,j}=1\ (i==j) f_{i,j}=\min(f_{i,j-1},f_{i+1,j})\ (i!=j,\ s_i==s_j) f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j})\ (i!=j,\ s_i!=s_j,\ i\le k<j)

由于f[i][j]的定义，我们可以知道f[1][n]即为答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[52];
int f[52][52];
int main() {
    int n;
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0x7F,sizeof(f));       //由于求最小，于是应初始化为大数
    for(int i=1;i<=n;++i)
        f[i][i]=1;
    for(int l=1;l<n;++l) 
        for(int i=1,j=1+l;j<=n;++i,++j) {
            if(s[i]==s[j])
                f[i][j]=min(f[i+1][j],f[i][j-1]);
            else
                for(int k=i;k<j;++k)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
    printf("%d",f[1][n]);
    return 0;
}