解题报告 P4170 [CQOI2007]涂色

题目内容

P4170

大意：给出一块木板，要求涂色，后覆盖前，求最小笔刷数

解题思路

区间 dp。

不难发现，定义状态 f_{i,j} 为 [i,j] 的最少次数可以满足最优子结构和无后效性，具体就是要看如何转移。

枚举端点 i，j，发现如果有 s_i=s_j 的话，相当于第一次涂色的时候多涂一格，转移方程为 f_{i,j}=\min(f_{i,j-1},f_{i+1,j})

但如果 s_i\neq s_j 的话，说明没办法直接多涂一格，需要枚举中间的断点 k，由于枚举 k 的过程中必然能找到一种划分方式使得总的涂色次数加起来最优，因此只需要将断点左右加起来取最小值就可以得到该区间的答案，故有如下方程：

f_{i,j}=\min_{k\in[i,j)} \lbrace f_{i,k}+f_{k+1,j}\rbrace

#include <cstdio>
#include <cstring>

int f[55][55];

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int n;
    char s[55];
    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 l=1;l<n;l++)
        for(int i=1,j=l+1;j<=n;i++,j++)
            if(s[i]==s[j])
                f[i][j]=min(f[i][j-1],f[i+1][j]);
            else
                for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    printf("%d\n",f[1][n]);
    return 0;
}