密码脱落

题目链接


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

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

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

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

你的任务是：

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

输入格式

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

输出格式

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

数据范围

输入字符串长度不超过1000

输入样例1：

ABCBA

输出样例1：

0

输入样例2：

ABDCDCBABC

输出样例2：

3

算法分析

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

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

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

另一种是区间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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
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<slen;l++)
        {
            int r=l+len-1;
            if(l==r)    dp[l][r]=1;
            else 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]);
            }
        }
    }
    cout<<slen-dp[0][slen-1]<<endl;
    return 0;
}

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

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
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<<slen-dp[slen][slen]<<endl;
    return 0;
}

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


参考题解

#include <iostream>
#include <cstdio>
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;
}