题目：http://acm.hdu.edu.cn/showproblem.php?pid=1243
思路：LCS简单变形。LCS模板：http://blog.csdn.net/chen_minghui/article/details/71773817
各种坑，用memset MLE ，不给数据范围。给跪了
#include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<iostream> #include<map> using namespace std; const int maxn = 3*1e3; int dp[maxn][maxn]; int main() { int n; // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int score[200]; char a[3000],b[3000],t[3000]; while(~scanf("%d",&n)) { int temp; scanf("%s",t); for(int i=0;i<n;i++) { scanf("%d",&temp); score[t[i]]=temp; } scanf("%s%s",a,b); for(int i=0;i<=n;i++) { dp[i][0]=0; dp[0][i]=0; } // memset(dp,0,sizeof(dp)); int len1=strlen(a); int len2=strlen(b); for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+score[a[i-1]]; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } printf("%d\n",dp[len1][len2]); } }