做一个网站链接怎么做/现在学seo课程多少钱
链接：点击打开链接
题意：给出一些字母两两匹配的值，给出两个串，要求再求出两个串使给出的两个串是这两个串的子序列并且匹配值最小
代码：
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
char s1[2005],s2[2005],s3[2005];
int in[2005],out[2005],val[2005][2005],dp[2005][2005],next[2005][2005];
int main(){ //和poj1080几乎一样，就是加了一个路径输出int i,j,k,l1,l2,l3,tmp,tmp1,tmp2,tmp3,num; //http://blog.csdn.net/stay_accept/article/details/51509685while(scanf("%s%s%s",s3+1,s1+1,s2+1)!=EOF){vector<char> a1,a2;l1=strlen(s1+1);l2=strlen(s2+1);l3=strlen(s3+1);memset(in,-1,sizeof(in));memset(out,-1,sizeof(out));memset(val,INF,sizeof(val));for(i=1;i<=l3;i++){for(j=1;j<=l3;j++){scanf("%d",&num);val[(int)s3[i]][(int)s3[j]]=num;if(in[(int)s3[i]]==-1||val[(int)s3[i]][in[(int)s3[i]]]>val[(int)s3[i]][(int)s3[j]])in[(int)s3[i]]=(int)s3[j];if(out[(int)s3[j]]==-1||val[out[(int)s3[j]]][(int)s3[j]]>val[(int)s3[i]][(int)s3[j]])out[(int)s3[j]]=(int)s3[i];}} //求出每个字母与哪一个字母匹配值最小dp[0][0]=0; //和被匹配时值最小for(i=1;i<=l1;i++){dp[i][0]=dp[i-1][0]+val[(int)s1[i]][in[(int)s1[i]]];next[i][0]=1;}for(i=1;i<=l2;i++){dp[0][i]=dp[0][i-1]+val[out[(int)s2[i]]][(int)s2[i]];next[0][i]=2;} //先初始化for(i=1;i<=l1;i++){for(j=1;j<=l2;j++){ //dp[i][j]表示第一个串匹配到i，第二个串匹配到jtmp1=dp[i-1][j]+val[(int)s1[i]][in[(int)s1[i]]];tmp2=dp[i][j-1]+val[out[(int)s2[j]]][(int)s2[j]];tmp3=dp[i-1][j-1]+val[(int)s1[i]][(int)s2[j]];tmp=min(tmp1,min(tmp2,tmp3));dp[i][j]=tmp;if(tmp==tmp1)next[i][j]=1;else if(tmp==tmp2)next[i][j]=2;elsenext[i][j]=3; //并记录前驱}}printf("%d\n",dp[l1][l2]);while(l1>0||l2>0){if(next[l1][l2]==1){a1.push_back(s1[l1]);a2.push_back((char)in[(int)s1[l1]]);l1--;}else if(next[l1][l2]==2){a1.push_back((char)out[(int)s2[l2]]);a2.push_back(s2[l2]);l2--;}else if(next[l1][l2]==3){a1.push_back(s1[l1]);a2.push_back(s2[l2]);l1--,l2--;}}for(i=a1.size()-1;i>=0;i--)printf("%c",a1[i]);printf("\n");for(i=a2.size()-1;i>=0;i--)printf("%c",a2[i]);printf("\n");}return 0;
}