X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。
你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。
输入一行,表示现在看到的密码串(长度不大于1000)
要求输出一个正整数,表示至少脱落了多少个种子。
例如,输入:
ABCBA
则程序应该输出:
0
再例如,输入:
ABDCDCBABC
则程序应该输出:
3
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 1000ms
#include<iostream>#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1010][1010];
string s;
int f(int p,int q){
if(p==q)return 0;// 指向同一个时返回0
if(q-p==1){//相隔1个位置
if(s[p]==s[q])return 0;//abba-->abba-->0
else return 1; //abca-->acbca-->1
}
if(s[p]==s[q]){//相同时p,q分别向前向后移
return f(p+1,q-1);
}
if(a[p][q]>0)return a[p][q];
//如果搜索过返回p,q之间的字符串的最小值
//(aabcab--(知道abca最小脱落数为1)a...b-->aa...bb为2,得1+1=2)
int x=f(p+1,q)+1;
int y=f(p,q-1)+1;
return a[p][q]=min(x,y);
}
int main(){
cin>>s;
memset(a,0,sizeof(a));
int x=f(0,s.length()-1);
cout<<x;
return 0;
}