网站贸易表格怎么做,泉州市建设局网站,个人做网站怎么赚钱,深圳关键词优化平台POJ 1159 Palindrome(字符串变回文:LCS) http://poj.org/problem?id1159 题意: 给你一个字符串, 问你做少须要在该字符串中插入几个字符能是的它变成一个回文串. 分析: 首先把原字符串和它的逆串进行匹配, 找出最长公共子序列. 那么最长公共子序列的字符串肯定是一个回文串. 所… POJ 1159 Palindrome(字符串变回文:LCS) http://poj.org/problem?id1159 题意: 给你一个字符串, 问你做少须要在该字符串中插入几个字符能是的它变成一个回文串. 分析: 首先把原字符串和它的逆串进行匹配, 找出最长公共子序列. 那么最长公共子序列的字符串肯定是一个回文串. 所以原串剩下的部分是不构成回文的. 我们仅仅须要加入剩下部分的字符到相应位置, 原串自然就变成了一个回文. 所以本题的解为: 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代码: #includecstdio
#includecstring
#includealgorithm
using namespace std;
const int maxn50005;int n;
char s1[maxn],s2[maxn];
int dp[2][maxn];int main()
{while(scanf(%d,n)1){scanf(%s,s1);for(int i0;in;i)s2[i]s1[n-1-i];memset(dp,0,sizeof(dp));for(int i1;in;i)for(int j1;jn;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
