密码脱落

X星球的考古学家发现了一批古代留下来的密码。

这些密码是由A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：

给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入格式

共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。

输出格式

输出一个整数，表示至少脱落了多少个种子。

数据范围

输入字符串长度不超过1000

输入样例1：

ABCBA

输出样例1：

输入样例2：

ABDCDCBABC

输出样例2：

算法分析

将当前字符串加上若干字母使其变为回文串,其实就是将多余的字母对应位置加上对应的字母.

所以这题也可以转化为删除多少字符使其变为回文串.

一种方法是将字符串倒转,求出他的最长公共子序列,这样就可以比较便利地求出来,最长组成回文串子序列的长度.

另一种是区间dp的方式,我们的思路是从两端向中间靠拢,选判断边界相等的问题.

如果边界两个字符是相等的,那么直接当前区间的最长回文串子序列+2,

如果是不相等的情况下,就要判断是包含左端点不包含右端点的长度长,还是包含右端点不包含左端点的长度长,

这一点的思路是和最长公共子序列的思路是一样的.

当然还有左右端点都不选的状态,但是选的话一定是大于等于的状态,所以就不用考虑都不选的情况了

所以转移方程就是

if(s[l]==s[r]) dp[l][r]=dp[l+1][r-1]+2;else{
         dp[l][r]=max(dp[l+1][r],dp[l][r]);      dp[l][r]=max(dp[l][r-1],dp[l][r]);}

代码实现

区间dp求最长回文子序列

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=1e3+5;int dp[maxn][maxn];int main(){
       string s;    cin>>s;    int slen=s.size();    for(int len=1;len<=slen;len++)    {
           for(int l=0;l+len-1

将字符串反转求最长回文子序列

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=1e3+5;int dp[maxn][maxn];int main(){
       string s;    cin>>s;    int slen=s.size();    string a=s;    reverse(a.begin(),a.end());    for(int i=1;i<=slen;i++)    {
           for(int j=1;j<=slen;j++)        {
               if(a[i-1]==s[j-1])                dp[i][j]=dp[i-1][j-1]+1;            else            {
                   dp[i][j]=max(dp[i-1][j],dp[i][j-1]);            }        }    }    cout<
       
        <

DFS做法,不间接求,直接是求使字符串变回文的思路,不过还是区间dp的思想

#include 
   
    #include 
    
     using namespace std;const int N = 1e3 + 5;int f[N][N];string str;int dfs(int l, int r){
       if (f[l][r])         return f[l][r];    if (l >= r)        return 0;    int res;    if (str[l] != str[r])        res = min(dfs(l, r-1)+1, dfs(l+1, r)+1);    else        res = dfs(l+1, r-1);    return f[l][r] = res;}int main(){
       cin >> str;    cout << dfs(0, str.size()-1);    return 0;}

转载地址：http://jhagz.baihongyu.com/

你可能感兴趣的文章