蓝桥杯 密码脱落【第七届】【省赛】【C组】C++ 动态规划

资源限制

时间限制：1.0s 内存限制：256.0MB

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

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

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

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

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

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

　　请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

　　所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

　　注意: main函数需要返回0
　　注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
　　注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

　　提交时，注意选择所期望的编译器类型。

要求至少脱落了多少字种子，转化成求所给字符串中的最长回文串。用所给字符串长度减去其中最长回文串长度，便得到其脱落的种子数。假设初始字符串为s

此题解利用动态规划法

dp[l][r]表示以为l为左边界，以r为右边界的字符串中的最长回文串长度。

dp[0][s.size()-1]即初始串中的最长回文串长度。

对于任意合法的dp[l][r]，其递推公式为

if(s[l]==s[r])dp[l][r]=dp[l+1][r-1]+2

else dp[l][r]=max(dp[l+1][r],dp[l][r-1])

记得初始化，任意的字符，其本身是长度为1的回文串。即dp[i][i]=1；

#include
using namespace std;
const int N = 1005;
string s;
int dp[N][N];//dp[i][j]表示，以i为起点，j为终点的字符串中的最长回文串长度
int main()
{
    cin >> s;
    int len = s.size();
    for (int i = 0; i< len; i++)dp[i][i] = 1;//本身显然为长度为1的回文串
    for (int tlen = 2; tlen <= len; tlen++)//枚举回文串的长度
        for (int l = 0; tlen + l - 1 < len; l++){//左边界从0开始枚举。当回文串的右边界，即tlen+l-1