http://acm.hdu.edu.cn/showproblem.php?pid=2476
题目大意是给定一个起始串和一个目标串，然后每次可以将某一段区间染成一种字符，问从起始串到目标串最少需要染多少步？
读完题首先会想到的自然是用区间dp，但是列出来发现，没办法区间合并。因为一旦需要考虑对某一段成段染色的话，在区间合并的时候，就无法考虑转移过程中起始串的变化了。
既然这样，就不考虑成段染色造成的影响了，就当起始串和目标串处处不想等。
那么考虑区间[i, i+len]，
自然遍历子区间[i, j]，
如果[i, j]和[j+1, i+len]需要合并的话，
如果考虑成段染色的话，只有str2[i] == str2[j+1]时，考虑成段染色[i, j+1]，但是[i, j+1]的父区间又有可能会成段然和str2[i]一样的颜色，所以不能直接将区间缩短成[i+1, j]和[j+2, i+len]，所以可以考虑这一步的效果只相当于染str2[j+1]的时候，可以少染一个str2[i]。那么区间就变成[i+1, j]和[j+1, i+len]， 这样父区间中可能再次出现一个i`，和j+1产生成段染色，即
p[i][i+len] = min(p[i][i+len], p[i+1][j]+p[j+1][i+len]);
然后就是考虑使用p来计算ans[i],表示前i个字符从起始串到目标串的步数。
ans[0]自然好考虑，只需要判断一下str1[0]和str2[0]。
对于ans[i]，
如果str1[i] == str2[i]，自然就可以退化成ans[i-1]。
其它情况，自然是遍历子区间ans[j]和p[j+1][i]进行合并。
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <queue> #include <map> #include <set> #include <string> #include <vector> using namespace std; char str1[105], str2[105]; int n, p[105][105], ans[105]; //p为不考虑初始串的情况,ans为考虑初始串的情况 void work() { for (int i = 0; i < n; ++i) p[i][i] = 1; int t; for (int len = 1; len < n; ++len) { for (int i = 0; i < n && i+len < n; ++i) { p[i][i+len] = p[i+1][i+len]+1; for (int j = i; j < i+len; ++j) if (str2[i] == str2[j+1]) p[i][i+len] = min(p[i][i+len], p[i+1][j]+p[j+1][i+len]); } } ans[0] = str1[0]==str2[0]?0:1; for (int i = 1; i < n; ++i) { ans[i] = str1[i]==str2[i]?ans[i-1]:p[0][i]; for (int j = 0; j < i; ++j) ans[i] = min(ans[i], ans[j]+p[j+1][i]); } printf("%d\n", ans[n-1]); } int main() { //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); while (scanf("%s%s", str1, str2) != EOF) { n = strlen(str1); work(); } return 0; }
ACM学习历程—HDU2476 String painter（动态规划）
原文：http://www.cnblogs.com/andyqsmart/p/5295297.html
