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

作者: wjyyy 分类: DP,区间DP,解题报告,贪心 发布时间: 2018-08-10 18:42

点击量:15

 

    区间特性很容易看出来,但是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;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Mayflyyh Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Mayflyyh
游客

是不是太强了一点?

/* */