蓝桥 区间dp
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子
输入
输入一行，表示现在看到的密码串（长度不大于1000）
输出
要求输出一个正整数，表示至少脱落了多少个种子。
样例输入
ABCBA
样例输出
0
解题报告：用区间dp找最长子序列，然后长度减去1~n的回文串就是答案了，dp时分为4种情况，当然不是每种情况都存在，如果区间左右端点相等那么就是dp[l+1][r-1]+2，如果左端点在里面就是dp[l][r-1]，当然这两个不是完全等价，但是右端点一定不在，dp最大值问题可以重复，但是不能遗漏，右端点也是一样做。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=1010;
int dp[N][N];
int main()
{
char s[N];
scanf("%s",s+1);
int n=0;
for(int i=1;s[i]!='\0';i++)
n++;
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++)
dp[i][i]=1;
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
// cout<<l<<' '<<r<<endl;
if(s[l]==s[r])
dp[l][r]=2+dp[l+1][r-1];
else
dp[l][r]=dp[l+1][r-1];
dp[l][r]=max(dp[l][r],max(dp[l+1][r],dp[l][r-1]));
}
cout<<n-dp[1][n]<<endl;
return 0;
}
