POJ 1159 Palindrome(最长公共子序列)-白红宇

POJ 1159 Palindrome(最长公共子序列)

阅读量：4707 次

发布时间：2019-06-10

本文共 1282 字，大约阅读时间需要 4 分钟。

Palindrome

【题目链接】

【题目类型】最长公共子序列

&题解：

你做的操作只能是插入字符,但是你要使最后palindrome,插入了之后就相当于抵消了,所以就和在这个串中删除最少的字符,使得它回文是一样的.

那么我们可以把这个串reverse,之后的串称为s2,找s2和s的最长公共子序列就好了,因为有了LCS,接着把其他的都删掉,就是一个回文串了,因为正着读和倒着读都一样
还有POJ居然能跑5000^2 我的923MS就跑完了,还是很快的嘛,当然这题还可以滚动数组,要对下标取模什么的也许就可以了吧,我用的是short来减小内存

&代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              using namespace std;#define INF 0x3f3f3f3f#define ll long long#define fo(i,a,b) for(int i=(a);i<=(b);i++)#define fd(i,a,b) for(int i=(a);i>=(b);i--)#define cle(a,v) memset(a,(v),sizeof(a))const int maxn = 5000 + 7;short n, dp[maxn][maxn];char s1[maxn], s2[maxn];int main() {#ifndef ONLINE_JUDGE freopen("E:1.in", "r", stdin);#endif while(~scanf("%d", &n)) { cle(dp, 0); scanf("%s", s1); strcpy(s2, s1); reverse(s2, s2 + n); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; 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]); } } // for(int i = 1; i <= n; i++) { // for(int j = 1; j <= n; j++) { // printf("%3d", dp[i][j]); // } // printf("\n"); // } printf("%d\n", n - dp[n][n]); } return 0;}