密码脱落

9.

 

密码脱落(后来难点就是有标题,测试用例不会有E出现)

 

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

那一个密码是由A、B、C、D 四种植物的种子串成的队列。

精心分析发现,那些密码串当初理应是前后对称的(相当于大家说的镜像串)。

出于年代久远,其中不少种子脱落了,因此可能会失掉镜像的特点。

 

你的天职是:

给定叁个现行观看的密码串,统计一下从当年的意况,它要至少脱落多少个种子,才或然会变成未来的典范。

 

输入一行,表示今后观察的密码串(长度不超过1000)

务求输出1个正整数,表示至少脱落了多少个种子。

 

例如,输入:

ABCBA

则程序应该出口:

0

 

再例如,输入:

ABECDCBABC

则程序应该出口:

3

 

财富约定:

峰值内存消耗 < 256M

CPU消耗 < 1000ms

 

请严厉按须要输出,不要画蛇添足地打印类似:“请你输入…” 的盈余内容。

 

抱有代码放在同八个源文件中,调试通过后,拷贝提交该源码。

 

专注:main函数需求再次回到0

注意: 只使用ANSI C/ANSI C++
标准,不要调用重视于编译环境或操作系统的独特函数。

留神: 全体正视的函数必须显然地在源文件中 #include <xxx>,
无法经过工程安装而省略常用头文件。

 

交付时,注意采取所梦想的编译器类型。

 

思路:

急需找出最少的字符去除使其变成回文串,思路就是将交给的字符串反转,三个字符串求出公共最长的子种类,就是原串最长的回文子连串的尺寸,再用原串的尺寸减去LCS的

长度即可。

LCS详解的传送门:1.点击打开链接 

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string s1,s2;
    cin>>s1;
    int len=s1.length();
    s2=s1;
    reverse(s1.begin(),s1.end());
    //二维数组解法
    int dp[len+1][len+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=len;j++)
        {
            if(s1[i-1]==s2[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    //一维数组解法
    int dp2[len+1];
    memset(dp2,0,sizeof(dp2));
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=len;j++)
        {
            if(s1[i-1]==s2[j-1])
                dp2[j]=dp2[j-1]+1;
            else
                dp2[j]=max(dp2[j-1],dp2[j]);
        }
    }
    printf("%d\n",len-dp[len][len]);
    printf("%d\n",len-dp2[len]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图