题目描述

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

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

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

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

你的任务是：

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

样例

案例一：
输入

ABCBA

输出

0

案例二:
输入

ABDCDCBABC

输出

3

解题思路（LCS—最长公共子序列）：

要求是对称，那我我们把原串翻转一下，那么原串的前半部分与翻转串的后半部分，翻转串的前半部分与原串的后半部分应该匹配上，那么可以匹配上的子序列都是原本存在的回文字符，那么用原串的长度减去两串的最长公共子序列就可以得知还需要添加多少字符才能整体回文
在进行对比可以发现两串有3个不同的字母,那么我们添加这三个字母不就好了。所以答案就是长度-LCS(最长公共子序列）。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int N = 10010;
int f[N][N];
//f[i][j]表示a[0 ~ i - 1] 和 b[0 ~ j - 1](前i个字符和前j个字符)所有公共子序列的最大值

int LCS(string a,string b){
    int len1 = a.length(),len2 = b.length();
    for(int i = 1;i <= len1;++i){
        for(int j = 1;j <= len2;++j){

            f[i][j] = max(f[i][j - 1],f[i - 1][j]);

            if(a[i - 1] == b[j - 1]){
                f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);
            }
        }
    }
    return f[len1][len2];
}


int main(){
    string str1;
    cin >> str1; //从下标1开始记录
    string restr1 = str1;
    reverse(restr1.begin(),restr1.end());
    int res = str1.length() - LCS(str1,restr1);
    cout << res << endl;
    return 0;
}