原文地址：http://blog.csdn.net/a601025382s/article/details/12379565 原文作者：knownothing

String painter

Time Limit: 5000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3815????Accepted Submission(s): 1782


Problem Description There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?
Input Input contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.

Output A single line contains one integer representing the answer.
Sample Input zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd
Sample Output 6 7

題意：給定兩個字符串a和b，求最少需要對a進行多少次操作，才能將a變成b。每次操作時將a中任意一段變成任意一個字母所組成的段。

題解：動態(tài)規(guī)劃題。dp[i][j]表示a中i到j段變成b需要的最少次數(shù)。遞推公式：dp[i][j]=min(dp[i][k]+dp[k+1][j])(i<=k<j)。接著就是判斷分界點了，對于字符串b，只有將相同字符一起刷才能減少操作數(shù)。所以每次碰到b[i]==b[k]時，可以減少一次操作，因為刷一次[i,k]再刷[i+1,k-1]和分別刷[i,i][k,k],[i+,k,k+1]是一樣的，可操作數(shù)會減少。

注意：由于如果一段子串兩端相等，會成端更新，從而改變中間子串的字符，所以處理時可假定所以a中單個字符都需要一次變化才能變成b。之后動態(tài)規(guī)劃完成后再處理a和b中形同位置相同字符的情況。

另一種理解方式：不考慮起始串，將起始串默認為空串，找出所有dp值(dp[i][j]表示i到j這段空子串轉換成目標串需要的最小次數(shù))后，再通過ans[i]來求得最小變換值。ans[i]表示前i+1長度的子串轉換成目標串需要的最小次數(shù)。

耗時：15MS/2000MS

#include <cstdio> #include <cstring> #include <cmath> #include <map> #include <iostream> #include <algorithm> using namespace std; const int maxn=110; int dp[maxn][maxn]; char a[maxn],b[maxn]; int ans[maxn]; int main() {while(cin>>a>>b){int i,j,k,n,m,p,q,len,t;n=strlen(a);memset(dp,0,sizeof(dp));//為處理方便，一個的時候都需要改變才能得到對應字母。//因為當一段被更新后，兩字符串原本相等的值就改變了。for(i=0;i<n;i++)dp[i][i]=1;for(len=2;len<=n;len++)//枚舉長度{for(i=0;i<n-len+1;i++)//枚舉起點{j=i+len-1;//終點//cout<<i<<" "<<j<<endl;dp[i][j]=dp[i+1][j]+1;//!!由于只有比較的是b[i]=b[k]，所以不能用dp[i][j]=dp[i][j-1]+1for(k=i+1;k<=j;k++)//枚舉分割點{if(b[i]==b[k]){//cout<<i<<" "<<k<<endl;dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);}}}}for(i=0;i<n;i++)ans[i]=dp[0][i];for(i=0;i<n;i++){//重新計算兩字符串中字符相同的點。if(a[i]==b[i]){if(i==0)ans[i]=0;else ans[i]=ans[i-1];}else{for(j=0;j<i;j++)ans[i]=min(ans[i],ans[j]+dp[j+1][i]);}}cout<<ans[n-1]<<endl;}return 0; }

轉載于:https://www.cnblogs.com/junior19/p/6730113.html

總結

以上是生活随笔為你收集整理的HDU2476：String painter（区间dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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