http://acm.hdu.edu.cn/showproblem.php?pid=2476

題目大意是給定一個起始串和一個目標(biāo)串，然后每次可以將某一段區(qū)間染成一種字符，問從起始串到目標(biāo)串最少需要染多少步？

讀完題首先會想到的自然是用區(qū)間dp，但是列出來發(fā)現(xiàn)，沒辦法區(qū)間合并。因?yàn)橐坏┬枰紤]對某一段成段染色的話，在區(qū)間合并的時候，就無法考慮轉(zhuǎn)移過程中起始串的變化了。

既然這樣，就不考慮成段染色造成的影響了，就當(dāng)起始串和目標(biāo)串處處不想等。

那么考慮區(qū)間[i,?i+len]，

自然遍歷子區(qū)間[i,?j]，

如果[i,?j]和[j+1,?i+len]需要合并的話，

如果考慮成段染色的話，只有str2[i]?==?str2[j+1]時，考慮成段染色[i,?j+1]，但是[i,?j+1]的父區(qū)間又有可能會成段然和str2[i]一樣的顏色，所以不能直接將區(qū)間縮短成[i+1,?j]和[j+2,?i+len]，所以可以考慮這一步的效果只相當(dāng)于染str2[j+1]的時候，可以少染一個str2[i]。那么區(qū)間就變成[i+1,?j]和[j+1,?i+len]，?這樣父區(qū)間中可能再次出現(xiàn)一個i`，和j+1產(chǎn)生成段染色，即

p[i][i+len]?=?min(p[i][i+len],?p[i+1][j]+p[j+1][i+len]);

然后就是考慮使用p來計算ans[i],表示前i個字符從起始串到目標(biāo)串的步數(shù)。

ans[0]自然好考慮，只需要判斷一下str1[0]和str2[0]。

對于ans[i]，

如果str1[i]?==?str2[i]，自然就可以退化成ans[i-1]。

其它情況，自然是遍歷子區(qū)間ans[j]和p[j+1][i]進(jìn)行合并。

?

代碼：

#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; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/andyqsmart/p/5295297.html

總結(jié)

以上是生活随笔為你收集整理的ACM学习历程—HDU2476 String painter（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。