本文主要是介绍Palindrome HDU - 1513（LCS 滚动数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Palindrome
HDU - 1513题意：给出一个字符串， 要求插入最少的字符使得该串成为回文串；
对给出串和它的反转串求一遍LCS， 串的长度减去LCS就是答案；
注意要用滚动数组， 否则会超内存；
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
string s1, s2;
int dp[2][5100];
int main(){while(~scanf("%d", &n)){cin >> s1;s2=s1;reverse(s2.begin(), s2.end());int k=1;memset(dp, 0, sizeof(dp));for(int i=0; i<=n; i++){for(int j=0; j<=n; j++){if(i==0||j==0) dp[k][j]=0;else{if(s1[i-1]==s2[j-1]) dp[k][j]=dp[!k][j-1]+1;else dp[k][j]=max(dp[!k][j], dp[k][j-1]);} }k=!k;}printf("%d\n", n-max(dp[0][n], dp[1][n]));}return 0;
}这篇关于Palindrome HDU - 1513（LCS 滚动数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
