广东品牌网站建设多少钱,邯郸微信公众号开发,静态网页毕业设计论文,网上商城推广方案题目描述 X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。 仔细分析发现#xff0c;这些密码串当初应该是前后对称的#xff08;也就是我们说的镜像串#xff09;。 由于年代久远#xff0c;其中许多种子脱落了#xff0c…题目描述 X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。 仔细分析发现这些密码串当初应该是前后对称的也就是我们说的镜像串。 由于年代久远其中许多种子脱落了因而可能会失去镜像的特征。 你的任务是给定一个现在看到的密码串计算一下从当初的状态它要至少脱落多少个种子才可能会变成现在的样子。 输入 输入存在多组测试数据对于每组测试数据输入一行表示现在看到的密码串长度不大于1000 输出 对于每组测试数据要求输出一个正整数表示至少脱落了多少个种子。 样例输入 ABCBA ABDCDCBABC 样例输出 0 3
解题思路 关键是找出最小的回文子串找到以后总数一减就可以知道脱落了几个问题转换成求原字符串与其反转字符串的最长公共子序列再用原长度减去。
最长公共子串序列求法 最长公共子序列-dp
代码如下
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 1010;
int dp[N][N];
string a;
int len;int main() {while (cin a) {memset(dp, 0, sizeof(dp));len a.length();string b a;reverse(b.begin(), b.end());for (int i 1; i len; i)for (int j 1; j len; j) {if (a[i - 1] b[j - 1])dp[i][j] dp[i - 1][j - 1] 1;elsedp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}cout len - dp[len][len] endl;}return 0;
}
