洛谷 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;
}
是不是太强了一点?
… [Trackback]
[…] There you will find 86018 more Info on that Topic: wjyyy.top/1271.html […]