蓝桥杯 2016省赛 C/C++ A T9

知识点

动态规划

题目

密码脱落

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

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

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

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

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

思路

首先考虑搜索方法，从字符串头和尾开始搜索，如果相同则分别向内前进一步，如果不同，即有一侧需要补充字符，由于题目只需要输出补充次数，所以只需要指针移动一位即可，取左部前进次数与右边前进次数的最小值。但此种方法复杂度为$2^n$，而n最大为1000，超时。

考虑字符串与逆序字符串的最长公共子序列，逆序字符串子序列中跳过的字符即是要补充的，字符串长度减去最长公共子序列即可得到答案。

代码

// 搜索方法 复杂度过高
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <sstream>

using namespace std;

int dfs(char *s,int left,int right,int cnt)
{
    if (left>=right) return cnt;
    if (*(s+left)!=*(s+right))
        return min(dfs(s,left+1,right,cnt+1),dfs(s,left,right-1,cnt+1));
    else
        return dfs(s,left+1,right-1,cnt);
}

char s[1000];

int main()
{
    scanf("%s",&s);
    int len=strlen(s);
    printf("%d\n",dfs(s,0,len-1,0));
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int lcs(string s1, string s2)
{
    int m=s1.length(),n=s2.length();
    vector<vector<int>> dp(m+1,vector<int>(n+1));

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (s1.at(i-1) == s2.at(j-1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }

    return dp[m][n];
}

int main()
{
    string s;
    cin >> s;
    string rev= s;
    reverse(rev.begin(),rev.end());
    cout << s.size() - lcs(s, rev);

    return 0;
}