题目描述

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

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

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

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

你的任务是：

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

输入格式

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

输出格式

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

数据范围

输入字符串长度不超过1000

输入样例1：

ABCBA

输出样例1：

0

输入样例2：

ABDCDCBABC

输出样例2：

3

主要考点

动态规划(区间DP)

类似题

石子合并
最长上升子序列

解题思路

动态规划            ------ 闫氏dp分析法

状态表示： f[l][r]
           集合：区间 [l, r] 所有子序列的长度的集合
           属性：最大值

状态计算：         ------- 集合的划分
           根据l, r 与区间 [l, r] 的位置关系进行划分
           1. l, r 均在区间 [l, r] 之中 if s[l] = = s[r] f[l][r] = f[l + 1][r - 1] + 2;
           2. l在区间 [l, r] 之中, f[l][r] = f[l, r - 1]
           3. r在区间 [l, r] 之中, f[l][r] = f[l + 1, r]
           4. l, r均不在区间 [l, r] 之中, f[l][r] = f[l + 1][r - 1]

C ++ 代码1

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

char s[N];
int f[N][N];//区间 [l, r] 中所有子序列的最大长度

int main(){
    scanf("%s", s);

    int n = strlen(s);

    for(int len = 1; len <= n; len ++){
        for(int l = 0; l + len - 1 < n; l ++){
            int r = l + len - 1;
            if(len == 1) f[l][r] = 1;
            else{
                if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;
                f[l][r] = max(f[l][r], f[l][r - 1]);
                f[l][r] = max(f[l][r], f[l + 1][r]);
            }
        }
    }

    printf("%d\n", n - f[0][n - 1]);

    return 0;
}

C ++ 代码2

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;

char s[N];
int f[N][N];
int ls;

int main(){
    cin >> s + 1;

    ls = strlen(s + 1);
    for(int i = 1; i <= ls; i ++) f[i][i] = 1;

    for(int len = 2; len <= ls; len ++){
        for(int l = 1; l + len - 1 <= ls; l ++){
            int r = l + len - 1;
            if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;
            f[l][r] = max(f[l][r], f[l][r - 1]);
            f[l][r] = max(f[l][r], f[l + 1][r]);
        }
    }

    cout << ls - f[1][ls] << endl;

    return 0;
}