「CQOI2007」「BZOJ1260」涂色paint （区间dp

1260: [CQOI2007]涂色paint

Time Limit: 30 Sec  Memory Limit: 64 MBSubmit: 2057  Solved: 1267[Submit][Status][Discuss]

Description

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。

Input

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

Output

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

Sample Input

 

Sample Output

【样例输入1】 AAAAA 【样例输入1】 RGBGR 【样例输出1】 1 【样例输出1】 3

HINT

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

---

题解

一道区间dp。

设F[L][R]为把[L,R]画完所需的最少次数。初始化F[i][j]=(j-i+1)，表示暴力的一格格涂。

转移时，在[L,R]上枚举两个断点（L',R'），表示在[L,R]上直接覆盖一个区间[L',R']。

一开始让F[L][R]=F[L][L'-1]+F[L'][R']+F[R'+1][R]，表示把大区间视为三个小区间，不在乎他们边界可能有缘。

如果L'上的颜色和L'-1相同，那么可以少画一次；如果R'上的颜色和R'+1相同，那么可以少画一次；如果L'-1上的颜色和R'+1上相同，那么又可以少画一次。

最后注意一下，因为假设在[L,R]上涂一层时，就算证明了这一层完全融入背景色，也不可能给原区间一个-1的buff，所以最多只能少画两次。

答案在F[1][n]。

我现在在怀疑是不是只用一个断点就可以解决问题

/************************************************************** Problem: 1260 User: qwerta Language: C++ Result: Accepted Time:76 ms Memory:1300 kb ****************************************************************/ #include<iostream> #include<cstring> #include<cstdio> using namespace std; char s[53]; int f[53][53]; int chek(int i,int j) { if(s[i]==s[j])return 1;//相同就可以少画一笔 else return 0; } int main() { //freopen("a.in","r",stdin); cin>>s; int n=strlen(s); for(int i=n;i;--i) s[i]=s[i-1]; for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) f[i][j]=(j-i+1);//预处理 for(int len=2;len<=n;++len) for(int l=1,r=len;r<=n;++l,++r) { for(int ll=l;ll<=r;++ll) for(int rr=ll;rr<=r;++rr) { int k=f[l][ll-1]+f[rr+1][r]+f[ll][rr],g=0; if(ll-1>=l)g+=chek(ll-1,ll);//左边界融入背景(///v///) if(rr+1<=r)g+=chek(rr,rr+1);//右边界融入背景(///v///) if(ll-1>=l&&rr+1<=r)g+=chek(ll-1,rr+1);//左右边界是一样哒！(>w<) k-=min(g,2);//最多只能少画两笔QAQ f[l][r]=min(f[l][r],k); } } cout<<f[1][n]; return 0; }

 

转载于:https://www.cnblogs.com/qwerta/p/9688214.html

相关资源：JAVA上百实例源码以及开源项目