首页 > 代码库 > hdu1513(最长公共子序列)
hdu1513(最长公共子序列)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1513
题意：将一个字符串转变为回文串的最少添加字符个数
分析：只要想到将字符串逆序后与原字符串求最长公共子序列，最少添加数为len-LCS，这题又是一道裸LCS。
这里还是要滚动数组优化空间才行。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;char s1[5110],s2[5110];int dp[2][5110];int main(){ int n; while(scanf("%d",&n)>0) { scanf("%s",s1); for(int i=1; i<=n; i++) { s2[i-1]=s1[n-i]; } memset(dp,0,sizeof(dp)); int cur=0,nxt=1; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(s1[i-1]==s2[j-1]) dp[nxt][j]=dp[cur][j-1]+1; else dp[nxt][j]=max(dp[nxt][j-1],dp[cur][j]); } swap(cur,nxt); } printf("%d\n",n-dp[cur][n]); }}
hdu1513(最长公共子序列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。