洛谷 P4170 [CQOI2007]涂色 题解【区间DP】【贪心】

点击量：236

    区间特性很容易看出来，但是DP就不一定了。。。

目录

题目描述

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。

 

每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。

 

用尽量少的涂色次数达到目标。

 

输入输出格式

输入格式：

输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

 

输出格式：

仅一行，包含一个数，即最少的涂色次数。

 

输入输出样例

输入样例#1：

AAAAA

输出样例#1：

1

输入样例#2：

RGBGR

输出样例#2：

3

说明

40%的数据满足：1<=n<=10

 

100%的数据满足：1<=n<=50

题解：

    这个题一上来就会贪心地把最下面一层填满，因此不容易想到DP，尤其是区间DP。不过这个题是可以合并两段的，在每一段处理之前是可以判断出这种情况的。

    对于这样的一个区间：

AABBCA

    在处理到[1,6]区间时，发现最右边一个点与最左边一个点相等，这时可以把[1,6]赋值为[1,5]，因为最左边是一定要刷的，如果一直刷到最右边，和只刷最左边或左边一部分没有什么影响，因此可以扩展。如果发现最右边一个点与右数第二个点相等，此时右数第二个点既然已经被染色，那它是可以扩展的。

    因为覆盖白色部分和覆盖蓝色部分都是覆盖，最终能达到相同的效果，那么我们就可以贪心的把这块板子全部刷成蓝色，接着转化为子问题去做。

Code：

#include<cstdio>
#include<cstring>
int Min(int x,int y)
{
    return x<y?x:y;
}
int f[51][51];
char clo[55];
int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%s",clo+1);
    int n=strlen(clo+1);
    for(int i=1;i<=n;i++)
        f[i][i]=1;
    for(int l=1;l<n;l++)//长度
        for(int i=1;i<=n-l;i++)//起点
        {
            if(clo[i]==clo[i+1]||clo[i]==clo[i+l])
                f[i][i+l]=f[i+1][i+l];
            if(clo[i+l]==clo[i+l-1]||clo[i+l]==clo[i])
                f[i][i+l]=Min(f[i][i+l],f[i][i+l-1]);
            for(int k=i;k<i+l;k++)//断点
                f[i][i+l]=Min(f[i][i+l],f[i][k]+f[k+1][i+l]);
        }
    printf("%d\n",f[1][n]);
    return 0;
}