首页 > 代码库 > hdu1243 最长公共子序列(LCS)
hdu1243 最长公共子序列(LCS)
原题地址
题目分析
这道题基本上是在普通LCS问题上的一点小小的变形,由求LCS的长度,改为求LCS的权值。架构还是不变的。可作为LCS问题的模板题。时间复杂度O(N^2)。
注意
题目中的字母都是小写字母,也就是只有26种字符。不需要开太大的数组。所以hash就是很好的一种保存权值的方法。另外吐槽一下。子弹序列和恐怖分子序列的长度太坑了,因为题目没有给出长度。我开了个2000个数组,wa了n次。改成2005就AC了。fuck。
代码
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[2005][2005]; char s[30],m[2005],k[2005]; int b[30]; int main() { int n; while(~scanf("%d",&n)) { scanf("%s",s); for(int i=0;i<n;i++) { scanf("%d",&b[s[i]-'a']); } scanf("%s%s",m,k); int n1=strlen(m); int n2=strlen(k); memset(dp,0,sizeof(int)*(n1+1)); for(int i=0;i<=n2;i++) dp[0][i]=0; for(int i=1;i<=n1;i++) { for(int j=1;j<=n2;j++) { if(m[i-1]==k[j-1]) dp[i][j]=dp[i-1][j-1]+b[m[i-1]-'a']; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } printf("%d\n",dp[n1][n2]); } }
解读
memset那句,就是给第0行清0。
m保存子弹序列,k保存恐怖分子序列。n1,n2分别是他们的长度。
dp[i][j]保留的是m[i-1]和k[j-1]的最大分数。所以最终的结果会保留在dp[n1][n2]中。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。