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

String painter

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6863 Accepted Submission(s): 3330

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串需要的最少操作次数

题解：首先考虑一个简化的问题，把一个空串涂改成B串需要的操作数，显然可以通过最基本的区间dp进行解决，转移方程为if(B[i]==B[k])dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j])；else dp[i][j]=min(dp[i][j],min(dp[i][k]+dp[k+1][j],dp[i][k-1]+dp[k][j]))；然后考虑A串不是空串，那么如果A[i]==B[i]，则有ans[i]=ans[i-1],如果A[i]!=B[i]，那么ans[i]=min(ans[j]+dp[j][i])。

普通的循环迭代版本

 #include<bits/stdc++.h>

 using namespace std;

 #define debug(x) cout<<"["<<#x<<"]"<<" is "<<x<<endl;

 char ch[],ch2[];

 int dp[][],ans[];

 const int inf=1e8;

 int main(){

     while(scanf("%s",ch+)!=EOF){

         scanf("%s",ch2+);

         int len=strlen(ch+);

         for(int i=;i<=len;i++){

             for(int j=;j<=len;j++){

                 if(i>j)dp[i][j]=;

                 else if(i==j)dp[i][j]=;

                 else dp[i][j]=inf;

             }

         }

         for(int i=;i<=len;i++){

             for(int j=;j+i-<=len;j++){

                 for(int k=j+;k<=j+i-;k++){

                     if(ch2[j]==ch2[k])dp[j][j+i-]=min(dp[j][j+i-],dp[j][k-]+dp[k+][j+i-]);

                     else dp[j][j+i-]=min(dp[j][j+i-],min(dp[j][k]+dp[k+][j+i-],dp[j][k-]+dp[k][j+i-]));

                 }

             }

         }

         for(int i=;i<=len+;i++){

             ans[i]=inf;

         }

         ans[]=;

         for(int i=;i<=len;i++){

             if(ch[i]==ch2[i]){

                 ans[i+]=min(ans[i+],ans[i]);

             }

             else{

                 for(int j=;j<=i;j++){

                     ans[i+]=min(ans[i+],ans[j]+dp[j][i]);

                 }

             }

         }

         printf("%d\n",ans[len+]);

     }

     return ;

 }

记忆化搜索版本(注意由于sol(1,len)只能保证dp[1][len]被更新，而不能保证所有的dp[i][j]被遍历到，所以需要使用n^2次sol(i,j)保证所有dp[i][j]都被更新了而不再是初始值)

 #include<bits/stdc++.h>

 using namespace std;

 #define debug(x) cout<<"["<<#x<<"]"<<" is "<<x<<endl;

 char ch[],ch2[];

 int dp[][],ans[];

 const int inf=1e8;

 int sol(int l,int r){

     if(dp[l][r]!=0x3f3f3f3f)return dp[l][r];

     if(l>r)return dp[l][r]=;

     if(l==r)return dp[l][r]=;

     for(int k=l+;k<=r;k++){

         if(ch2[k]==ch2[l]){

             dp[l][r]=min(dp[l][r],sol(l+,k)+sol(k+,r));

         }

         else{

             dp[l][r]=min(dp[l][r],sol(l+,r)+);

         }

     }

     return dp[l][r];

 }

 int main(){

     while(scanf("%s",ch+)!=EOF){

         scanf("%s",ch2+);

         int len=strlen(ch+);

         memset(dp,0x3f3f3f3f,sizeof(dp));

         for(int i=;i<=len;i++){

             for(int j=i;j<=len;j++){

                 sol(i,j);

             }

         }

        // sol(1,len);

         for(int i=;i<=len+;i++){

             ans[i]=0x3f3f3f3f;

         }

         ans[]=;

         for(int i=;i<=len;i++){

             if(ch[i]==ch2[i]){

                 ans[i+]=min(ans[i+],ans[i]);

             }

             else{

                 for(int j=;j<=i;j++){

                     ans[i+]=min(ans[i+],ans[j]+dp[j][i]);

                 }

             }

         }

         printf("%d\n",ans[len+]);

     }

     return ;

 }

巴特西

[一道区间dp][String painter]

String painter

最新文章

热门文章