密码脱落——蓝桥杯

密码脱落

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。

例如，输入：
ABCBA
则程序应该输出：
0

再例如，输入：
ABDCDCBABC
则程序应该输出：
3

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>，不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。

----------------------------------------------------------------------------------------------------------------------------

涉及到动态规划问题。受下面的博客的影响：

blog.csdn.net/summonlight/article/details/61427968

感觉他的代码不是特别好理解，但是如果想理解下面的代码，建议还是看他的博客以及里面的链接。

以下是我改的：

#include "stdafx.h"
#include <iostream>
#include <vector>
#include<cmath>
#include<string>
using namespace std;

int dp[100][100];
int _tmain(int argc, _TCHAR* argv[])
{
        char s[]="ABDCDCBABC";
int n=strlen(s);//字符串长度

for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            if (s[i]==s[n-j-1]) {
                dp[i+1][j+1]=dp[i][j]+1;//dp[i,j]其实是(i,j)的不包括自己
            } else {
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    cout<<n-dp[n][n];
return 0;
}

由于对称，将原字符串跟逆序字符串进行比较，来求最大公共子序列（不是串，可以是不连续的）。

dp[i+1][j+1]保存的是原串的i号位置之前的所有字符跟逆序串的j号位置之前的所有字符的最大公共子序列（包括i,j号位置）。

上面的博客是从i=1开始进行处理，

dp[i][j]=dp[i-1][j-1]+1;

我是觉得从i=1开始不太好理解，于是从0开始。

dp[i+1][j+1]=dp[i][j]+1;

最后用当前字符串长度n减去dp[n][n]就是结果，这里dp[n][n],因为字符串的最后一个元素就是s[n-1],dp[n][n]是对所有字符进行计算之后的结果。

由于数据有限，如果有问题希望大家能指出来。

秒客网

密码脱落——蓝桥杯

相关文章