POJ 1159 Palindrome(字符串變回文:LCS)

http://poj.org/problem?

id=1159

題意:

?????? 給你一個字符串, 問你做少須要在該字符串中插入幾個字符能是的它變成一個回文串.

分析:

?????? 首先把原字符串和它的逆串進行匹配, 找出最長公共子序列. 那么最長公共子序列的字符串肯定是一個回文串. 所以原串剩下的部分是不構成回文的. 我們僅僅須要加入剩下部分的字符到相應位置, 原串自然就變成了一個回文.

?????? 所以本題的解為: n 減去 (原串與逆串的LCS長度).

?????? 令dp[i][j]==x表示串A的前i個字符與串B的前j個字符的子串的最長公共子序列LCS.

?????? 初始化: dp全為0.

?????? 狀態轉移:

?????? A[i]==B[j]時: dp[i][j] = ?dp[i-1][j-1]+1.

?????? A[i]!=B[j]時: dp[i][j] = max( dp[i-1][j] , dp[i][j-1] ).

?????? 終于所求: dp[n][m].

?????? 程序實現用的2維滾動數組, 假設用int[5000][5000]會超內存.

AC代碼:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=5000+5;int n; char s1[maxn],s2[maxn]; int dp[2][maxn];int main() {while(scanf("%d",&n)==1){scanf("%s",s1);for(int i=0;i<n;i++)s2[i]=s1[n-1-i];memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(s1[i-1]==s2[j-1])dp[i%2][j]=dp[(i-1)%2][j-1]+1;elsedp[i%2][j]=max(dp[(i-1)%2][j] , dp[i%2][j-1]);}printf("%d\n",n-dp[n%2][n]);}return 0; }

轉載于:https://www.cnblogs.com/yangykaifa/p/7150890.html

總結

以上是生活随笔為你收集整理的POJ 1159 Palindrome(字符串变回文:LCS)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。