这道题染色我想是一个非常经典的问题 任意染色如何染成目标颜色 呢？
这就很 至少我们有 一种做法 两边都相等的话可以第一次染的时候全染就可以减少染色次数一次了。
这个经典的模型其实是一个区间dp 由小区间的染色扩展到大区间的染色 我虽想到了区间dp 但是状态的转移并不是很好想。
首先 设 f[i][j]表示 从第i到j这个区间中最少的染色次数 显然 f[i][i]=1;
然后便是 状态转移了 if(a[i]==a[j]) f[i][j]=min(f[i][j],f[i+1][j]);
else f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); 这个 真的我对其正确性其实并不是很敏感。但是由小区间推到大区间还是正确的 仔细想想dp 的状态
其实这样很是非常合理的 我是指如果两边都不相等的话我第一次全部染色是没有什么意义的 不如找一个断点取得最优方案。
很自然 对很自然。。。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<ctime> #include<queue> #include<stack> #include<vector> #include<cctype> #include<utility> #include<algorithm> #include<cstring> #include<string> #include<map> #include<set> #include<bitset> #include<deque> #include<cstdlib> #define mod 2009 #define INF 2147483646 #define ll long long #define db double using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[70]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=52; int n; char ch[MAXN]; int f[MAXN][MAXN]; inline int min(int x,int y){return x>y?y:x;} int main() { //freopen("1.in","r",stdin); scanf("%s",ch+1); n=strlen(ch+1); memset(f,10,sizeof(f)); for(int i=1;i<=n;++i)f[i][i]=1; for(int len=2;len<=n;++len) for(int i=1;i<=n-len+1;++i) { int j=i+len-1; if(ch[i]==ch[j])f[i][j]=min(f[i][j],f[i+1][j]); else for(int k=i;k<j;++k)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } put(f[1][n]); return 0; }
这个问题就是升级版的了 将给定子串 染色成目标子串。有些困难。。但是仍是自己乱搞搞出来了QAQ
我自己都觉得有点神奇了，首先不再是将上述子串染成它本身了 但是我们仍可以直接考虑将其染成 答案颜色（不考虑初始颜色的情况之下）。
有了这个 f[i][j] 表示第i个字符 到第j个染色成功的最小次数的话 （这样进一步为我们的乱搞提供了基础）
先是 应再次进行线性dp ans[i] 表示前i个字符被染好颜色的最小次数 因为 如果我们子串和目标串如果颜色是一致的 那么染色就变得没有什么意义了。
所以 if(ch[i]==ch1[i]) 那么此时考虑 当前颜色不染再次寻找断点 首先 我们必须要明确一个概念那就是 不染色比染色要少一个字符
也就是说 仅针对当前这个字符 不染色的代价一定是<=染色的代价的 我指的是前i个字符的时候把前面当做一个整体。
所以 可以有状态转移 ans[i]=min(ans[i],ans[j]+f[j+1][i]); 至于细节处理详见代码这样做的正确性。
我只是迷迷瞪瞪的写出来状态 但是 正确性 从理性上来说 我想是便利到了整个状态空间 把所有可能的最优解都便利到了。
从必要性来说 是为了求出最优答案我们唯一的方法就是寻找断点然后 取染色最优解。
从感性上说那就是 相信状态的最优性 也相信状态转移的合法性。（我经常问自己 你相信自己的状态和状态转移么？）
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cmath> #include<cstdio> #include<ctime> #include<queue> #include<stack> #include<vector> #include<cctype> #include<utility> #include<algorithm> #include<cstring> #include<string> #include<map> #include<set> #include<bitset> #include<deque> #include<cstdlib> #define mod 2009 #define INF 2147483646 #define ll long long #define db double using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[70]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=202; int n; char ch[MAXN],ch1[MAXN]; int f[MAXN][MAXN]; int ans[MAXN]; inline int min(int x,int y){return x>y?y:x;} int main() { //freopen("1.in","r",stdin); while(scanf("%s",ch+1)==1) { scanf("%s",ch1+1); n=strlen(ch+1); memset(f,10,sizeof(f)); memset(ans,10,sizeof(ans)); ans[0]=0; for(int i=1;i<=n;++i)f[i][i]=1; for(int len=2;len<=n;++len) for(int i=1;i<=n-len+1;++i) { int j=i+len-1; if(ch1[i]==ch1[j])f[i][j]=min(f[i][j],f[i+1][j]); else for(int k=i;k<j;++k)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); } for(int i=1;i<=n;++i)//ans表示前i个字符刷好的最小次数 { if(ch[i]==ch1[i]){for(int j=0;j<i-1;++j)ans[i]=min(ans[i],ans[j]+f[j+1][i-1]);ans[i]=min(ans[i],ans[i-1]);} else for(int j=0;j<i;++j)ans[i]=min(ans[i],ans[j]+f[j+1][i]); } put(ans[n]); } return 0; }
我相信 这是正确的！
这个可能是我为数不多的值得我骄傲的题目了。。。
从大体思路到细枝末节 都是自己想出来的 。
如果你做过前两题再做这道题会觉得非常简单 但是 如果直接上这道题呢 我觉得不太好想。
首先对于染色答案的统计 我就不太会，那不想染色答案怎么得到 我想设计什么样的状态才能获得最终答案。
显然 根据答案就是答案的原则 每次染色为k 且为环 这环也不是很友好啊，破环成链 还是复制两倍？
复制两倍显然无法统计答案 破环成链吧 这样的话 两次dp？ 我不知强制选择第一个点和最后点相连怎么搞。
果断弃疗 这时其实还有 一种非常暴力的做法 n次dp 即可 诱人 直接暴力一点的统计答案
设状态 f[i]表示前 i个 字符所染好色的最小次数根据 答案就是答案的最优性原则 我们可以知道
对于一个真正的答案是一条链上（已解决）几个<=k长度的段组成的
那么显然 f[i]=max(f[i],f[j]+cost[j+1][i]); 这就完成了最终答案的统计 复杂度 n^3能过诶
关键是求出 cost i j 这个怎么求 仔细观察发现 这个cost i j 就是我们对于长度<=k的答案 也就是说成功的转换到了第一道题目的模型。
成功解决。。心路历程比较心酸。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define INF 2147483646 #define ll long long #define R register using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } inline void put(int x) { x<0?putchar('-'),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+'0',x/=10; num==0?putchar('0'):0; while(num)putchar(ch[num--]); putchar(' ');return; } const int MAXN=202; int n,m,k,minn=INF; int a[MAXN<<1],f[MAXN<<1]; int cost[MAXN<<1][MAXN<<1]; inline int min(int x,int y){return x>y?y:x;} //f[i] 表示前i 个珠子全部染色完毕所需的最小次数 // f[i]=min(f[i],f[i-k]+cost[i-k+1][j]); int main() { //freopen("1.in","r",stdin); n=read();m=read();k=read(); memset(cost,10,sizeof(cost)); for(int i=1;i<=n;++i)a[i]=read(),a[i+n]=a[i]; for(int i=1;i<=(n<<1);++i)cost[i][i]=1; for(int len=2;len<=k;++len) { for(int i=1;i<=(n<<1)-k+1;++i) { int j=i+len-1; if(a[i]==a[j])cost[i][j]=min(cost[i][j],cost[i][j-1]); else for(int w=i;w<j;++w)cost[i][j]=min(cost[i][j],cost[i][w]+cost[w+1][j]); } } for(int p=1;p<n;++p) { memset(f,10,sizeof(f));f[p-1]=0; for(int i=p;i<=n+p-1;++i) { for(int j=max(p-1,i-k);j<i;++j) { f[i]=min(f[i],f[j]+cost[j+1][i]); } } minn=min(minn,f[n+p-1]); } put(minn); return 0; }
成功！