首页 > 代码库 > hdu1243（最长公共子序列变形）
hdu1243（最长公共子序列变形）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1243
分析：dp[i][j]表示前i个子弹去炸前j个恐怖分子得到的最大分。其实就是最长公共子序列加每个字母值为1，这里每个字母代表的值变化了一下。
状态转移方程：if(s1[i-1]==s2[j-1])dp[nxt][j]=dp[cur][j-1]+val[s1[i-1]];
else dp[nxt][j]=max(dp[nxt][j-1],dp[cur][j]);
#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[2110],s2[2110],str[2110];int dp[2][2110],val[200];int main(){ int n; while(scanf("%d",&n)>0) { scanf("%s",str); memset(val,0,sizeof(val)); for(int i=1;i<=n;i++)scanf("%d",&val[str[i-1]]); scanf("%s%s",s1,s2); int len1=strlen(s1); int len2=strlen(s2); memset(dp,0,sizeof(dp)); int cur=0,nxt=1; for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(s1[i-1]==s2[j-1]) { dp[nxt][j]=dp[cur][j-1]+val[s1[i-1]]; } else dp[nxt][j]=max(dp[nxt][j-1],dp[cur][j]); } swap(cur,nxt); } printf("%d\n",dp[cur][len2]); }}
hdu1243（最长公共子序列变形）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。