首页 > 代码库 > HDU 1513 Palindrome（最长公共子序列）

HDU 1513 Palindrome（最长公共子序列）

2024-07-03 07:06:10   225人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1513

解题报告：给定一个长度为n的字符串，在这个字符串中插入最少的字符使得这个字符串成为回文串，求这个最少的个数是多少？

一开始以为只是一个普通的DP题，但是按照我的想法敲出来之后怎么样都W了，无奈搜了解题报告，得知其实这个就是一个最长公共子序列问题，就是求这个字符串跟它的逆序的

字符串的最长公共子序列。因为杭电的题内存都要求在32M内存以内，所以很开心的敲出来才发现10^6的数组都开不了，所以只好寻求空间压缩的方法，一开始就觉得是用滚动数组，但看了很久就是没看出来。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#include<cstdlib>
using namespace std;
const int maxn = 5005;

int dp[2][maxn];
char str[maxn];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%s",str+1);
        memset(dp,0,sizeof(dp));
        int flag = 1;
        for(int i = 1;i <= n;++i)
        {
            flag = !flag;
            for(int j = 1;j <= n;++j)
            {
                if(str[i] == str[n-j+1])
                dp[flag][j] = dp[!flag][j-1]+1;
                else dp[flag][j] = max(dp[!flag][j],dp[flag][j-1]);
            }
        }
        printf("%d\n",n-dp[flag][n]);        
    }
    return 0;
}
View Code

 


联系
我们