uva 10739【基础(区间)dp】

题意：给定字符串，可以增加、删除、修改任意字符，问最少经过多少次操作使字符串回文。

题解：定义dp[l][r]表示把从l到r的子串Sl...Sr变成回文串需要操作的最少次数。字符可以增删改，有的博客说增删是一样的，有的说增比删开销大，我倾向于后者，但前者是对的。因为显然s[l]==s[r]时，dp[l][r]=dp[l+1][r-1];当两者不相等时，可以删去s[l]或者s[r],状态转移到dp[l+1][r]+1或dp[l][r-1]+1,但是增加怎么加？一样的，在状态dp[l][r-1]的左边添加's[l-1]'=s[r]，或在状态dp[l+1][r]的右边添加's[r+1]'=s[l]，画图看看，这和删除确实一样;自然，也可以把s[l],s[r]修改成相同的，状态转移到dp[l+1][r-1]+1。

直接循环里dp:

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int dp[][];

 char s[];

 int Min(int a,int b,int c)

 {

     int t=min(a,b);

     return min(t,c);

 }

 int main()

 {

     int T;

     cin>>T;

     for(int cas=;cas<=T;cas++)

     {

         cin>>s;

         int len=strlen(s);

         for(int i=;i<len;i++) dp[i][i]=;

         for(int i=len-;i>=;i--){

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

                 if(s[i]==s[j]) dp[i][j]=dp[i+][j-];

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

             }

         }

         cout<<"Case "<<cas<<": "<<dp[][len-]<<endl;

     }

     return ;

 }

或者记忆化搜索(dfs）：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int dp[][];

 char s[];

 int dfs(int l,int r)

 {

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

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

     if(s[l]==s[r])

         dp[l][r]=dfs(l+,r-);

     else

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

     return dp[l][r];

 }

 int main()

 {

     int T;

     cin>>T;

     for(int cas=;cas<=T;cas++)

     {

         cin>>s;

         int len=strlen(s);

         memset(dp,-,sizeof(dp));

         cout<<"Case "<<cas<<": "<<dfs(,len-)<<endl;

     }

     return ;

 }

巴特西

uva 10739【基础(区间)dp】

最新文章

热门文章