P8638 [蓝桥杯 2016 省 A] 密码脱落【LCS】
P8638 [蓝桥杯 2016 省 A] 密码脱落
题目描述
X 星球的考古学家发现了一批古代留下来的密码。
这些密码是由 A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的回文串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式
输入一行，表示现在看到的密码串。（长度不大于1000 10001000）
输出格式
要求输出一个正整数，表示至少脱落了多少个种子。
输入输出样例 #1
输入 #1
ABCBA输出 #1
0输入输出样例 #2
输入 #2
ABDCDCBABC输出 #2
3说明/提示
蓝桥杯 2016 年省赛 A 组 I 题。
问题链接：P8638 [蓝桥杯 2016 省 A] 密码脱落
问题分析：LCS问题，不解释。
参考链接：LQ0125 密码脱落【LCS】
题记：（略）
AC的C++语言程序如下：
/* LQ0125 密码脱落 */#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1000;intdp[N+1][N+1];intlcs(string a,string b){memset(dp,0,sizeofdp);intlena=a.length();intlenb=b.length();for(inti=0;i<lena;i++)for(intj=0;j<lenb;j++)if(a[i]==b[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);returndp[lena][lenb];}intmain(){string s;while(cin>>s){string t=s;reverse(t.begin(),t.end());cout<<t.length()-lcs(s,t)<<endl;}return0;}