BZOJ 1260: [CQOI2007]涂色paint
Description
假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。
Input
输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
Output
仅一行，包含一个数，即最少的涂色次数。
【样例输入1】
AAAAA
【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
HINT
40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50
题解
P.S.这么水的题目竟然想了许久。。。。。。
f[l][r]表示l~r的最小染色次数，然后能合并就合并！
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; int l; int f[55][55]; string s; inline int remin(int a,int b){return (a<b?a:b);} int main(){ cin>>s; l=s.length(); memset(f,127,sizeof(f)); for (int i=1;i<=l;i++) f[i][i]=1; for (int len=1;len<=l;len++){ for (int left=1;left<=l;left++){ if (left+len>l) break; int right=left+len; if (s[left-1]==s[right-1]){ if (len==1) { f[left][right]=1; }else{ f[left][right]=remin(remin(f[left+1][right],f[left][right-1]),f[left+1][right-1]+1); } }else{ for (int mid=left;mid<right;mid++){ f[left][right]=remin(f[left][right],f[left][mid]+f[mid+1][right]); } } } } printf("%d\n",f[1][l]); return 0; } |
原文链接：BZOJ 1260: [CQOI2007]涂色paint
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!