本文主要是介绍BZOJ 1260 [CQOI2007]涂色paint 记忆化搜索/dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。
Input
输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
Output
仅一行，包含一个数，即最少的涂色次数。
Sample Input
Sample Output
【样例输入1】
AAAAA
【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
AAAAA
【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
HINT
40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50
Source
题目链接
先补一句……就是如何把输入的字符数组s往后移动一位。
我们知道s是从0开始的……其实只要
scanf("%s",s+1);
int len=strlen(s+1)；
就可以了。
比较懒了……直接写记忆化了。
因为这种区间类dp记忆化搜索其实是非常好写的…
dp的话，，我就口胡一下吧。。
dp[L][R] L~R涂色最少次数。
对于L>R，dp[L][R]=正无穷；
对于L<R：
用tmp暂且记录一下（后面判断min）
考虑两端，如果L和L+1的颜色一样，那么tmp=min(tmp,dp[L+1][R]);
同理地，如果说R和R-1的颜色一样，tmp=min(tmp,dp[L][R-1])；
如果L和R的颜色一样，那么tmp=min(tmp,dp[L][R-1],dp[L+1][R]);
如果都不满足，找一个切分点k，我们判断dp[L][k]+dp[k+1][R]的最小值。
然后dp[L][R]=tmp即可。
对于L=R:
dp[L][R]=1。
那么就是一个简单的区间dp……
从长度从小到大dp。
好吧我写了记忆化搜索……事实上和dp的思想是一致的了。
区间动态规划的练手好水题。
#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=55;
int f[N][N];
char s[N];
int solve(int l,int r){if (l==r) return 1;if (~f[l][r]) return f[l][r];int mi=100;if (s[l]==s[r]) return min(solve(l+1,r),solve(l,r-1));if (s[l]==s[l+1]) return solve(l+1,r);if (s[r-1]==s[r]) return solve(l,r-1);for (int k=l;k<r;k++)mi=min(mi,solve(l,k)+solve(k+1,r));f[l][r]=mi;return mi;
}
int main(){scanf("%s",s+1);memset(f,255,sizeof(f));int len=strlen(s+1);printf("%d\n",solve(1,len));return 0;
}这篇关于BZOJ 1260 [CQOI2007]涂色paint 记忆化搜索/dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
