hdu_1513_Palindrome(LCS+滚动数组)

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

题意：给你一个字符串，问你最少插入多少个字符使其为回文字符。

题解：将字符串倒着保存，然后求一下原串和该串的最长公共子序列，然后字符串长度剪LCS就是答案

 1 #include<cstdio>
 2 #define FFC(i,a,b) for(int i=a;i<=b;i++)
 3 int n,dp[2][5010];
 4 char a[5010],b[5010];
 5 void fuck(){
 6     FFC(i,0,n)dp[0][i]=0,dp[1][i]=0;
 7     FFC(i,1,n)FFC(j,1,n)
 8     if(a[i]==b[j])dp[i%2][j]=dp[(i-1)%2][j-1]+1;
 9     else dp[i%2][j]=dp[(i-1)%2][j]>dp[i%2][j-1]?dp[(i-1)%2][j]:dp[i%2][j-1];
10 }
11 int main(){
12     while(~scanf("%d",&n)){
13         scanf("%s",a+1);
14         for(int i=1,j=n;i<=n;i++,j--)b[j]=a[i];
15         fuck();
16         printf("%d
",n-dp[n%2][n]);
17     }
18     return 0;
19 }

View Code