http://poj.org/problem?id=1159
题意:给定一个字符,问最少插入多少字符,使该字符串变成回文字符串。
思路:设原字符串序列为X,其逆字符串为Y,则最少插入的字符数=length(X)-X与Y的最长公共子序列的长度。
求LCS的状态转移方程为 max(dp[i-1][j],dp[i][j-1]) s1[i-1]!=s2[j-1]
dp[i][j] =
dp[i-1][j-1]+1; s1[i-1]==s2[j-1];
由于数据范围大,本题使用的滚动数组。
1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <string> 5 #include <sstream> 6 #include <cstring> 7 8 using namespace std; 9 int dp[2][5005]; 10 int main() 11 { 12 string s1,s2; 13 int n; 14 while(cin>>n) 15 { 16 cin>>s1; 17 s2 = s1; 18 reverse(s1.begin(),s1.end()); 19 memset(dp,0,sizeof(dp)); 20 for (int i = 1; i <= n; i ++) 21 { 22 for (int j = 1; j <= n; j ++) 23 { 24 if (s1[i-1]==s2[j-1]) 25 dp[i%2][j] = dp[(i-1)%2][j-1]+1; 26 else 27 dp[i%2][j] = max(dp[(i-1)%2][j],dp[i%2][j-1]); 28 } 29 } 30 int ans = n-dp[n%2][n]; 31 cout<<ans<<endl; 32 } 33 return 0; 34 }