String painter （区间dp）-白红宇

String painter （区间dp）

阅读量：4951 次

发布时间：2019-06-11

本文共 1594 字，大约阅读时间需要 5 分钟。

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?

InputInput 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.

OutputA single line contains one integer representing the answer.Sample Input

zzzzzfzzzzzabcdefedcbaababababababcdcdcdcdcdcd

Sample Output

67 区间dp，但是具体实现，没实现，参考了一下题解：链接：https://blog.csdn.net/martinue/article/details/45953229 代码:

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               const int maxn=1e5+5;typedef long long ll;using namespace std;int a[105],dp[105][105];char s1[105],s2[105];int solve(int i,int j){ if(dp[i][j]!=-1) return dp[i][j]; if(i>j) return dp[i][j]=0; if(i==j) return dp[i][j]=1; dp[i][j]=solve(i+1,j)+1; for(int k=i+1;k<=j;k++) if(s2[k]==s2[i]) dp[i][j]=min(solve(i+1,k)+solve(k+1,j),dp[i][j]); return dp[i][j];} int main (){ while(cin>>s1>>s2) { memset(dp,-1,sizeof(dp));memset(a,0,sizeof(a)); int len =strlen(s1); for(int i=0;i

转载于:https://www.cnblogs.com/Staceyacm/p/10829938.html

你可能感兴趣的文章