题目链接

1222. 密码脱落

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

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

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

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

你的任务是：

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

输入格式

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

输出格式

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

数据范围

输入字符串长度不超过1000

输入样例1：

ABCBA

输出样例1：

0

输入样例2：

ABDCDCBABC

输出样例2：

3

解题思路

区间dp

题目可以转化为将一个字符串转换为回文串至少需要插入或删除多少个字符，也可以认为求字符串的最长回文串，其余字符插入或者删除

• 状态表示：\(f[i][j]\) 表示区间 \([l,r]\) 内使其成为回文串至少需要插入或删除的字符个数

• 状态计算：

• • \(s[i]==s[j]\) 时，\(f[i][j]=f[i+1][j-1]\)
• • \(s[i]\neq s[j]\) 时，\(f[i][j]=min(f[i+1][j],f[i][j-1])+1\)

• 时间复杂度：\(O(n^2)\)

代码

// Problem: 密码脱落
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1224/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1005;
int f[N][N];
string s;
int main()
{
    cin>>s;
    int n=s.size();
    s=' '+s;
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) 
    	f[i][i]=0;
    for(int len=2;len<=n;len++)
    	for(int l=1;l+1<=n;l++)
    	{
    		int r=l+len-1;
    		if(s[l]==s[r])
    		{
    		    if(len!=2)
    		        f[l][r]=f[l+1][r-1];
    		    else
    		        f[l][r]=0;
    		}
    		else
    			f[l][r]=min(1+f[l+1][r],1+f[l][r-1]);
    	}
    cout<<f[1][n];
    return 0;
}