首页 > 代码库 > sgu-214 Weird Dissimilarity
sgu-214 Weird Dissimilarity
题目大意:
给你一个字符串Σ,我们假设它的长度为L,然后再给你两个字符串λ,γ,接下来就是一个L*L的矩阵,i行j列表示Σ[i]变换成Σ[j]的花费。
然后要你求出两个长度相等的字符串a,b,使得λ是a的子串,γ是b的子串,然后使得a[i]变换成b[i]的花费总和最小,输出最小花费和a,b。
解题思路:
很明显的DP题,和LCS很像,定义f[i][j]表示a的前i个与b的前j个转换的最小花费,然后我们预处理出一个min表示λ[i]、γ[i]空匹配的最小花费和对应的字符,之后转移方程很简单:
f[i][j]=MIN{ f[i-1][ j-1] + λ[i]和γ[ j ]匹配的花费 (j>0 && i>0),f[i-1][ j ]+minl[ i ] (i>0),f[i][ j-1]+ming[ j ] (j>0) }
然后输出的话就不再赘述了。
AC代码:
#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)>(b)?(b):(a)) using namespace std; char xigema[2010]="\0"; char lambda[2010]="\0",gama[2010]="\0"; int cost[2010][2010]={{0}}; struct o_o { int mcost; int u; }minl[2010]={{0,0}},ming[2010]={{0,0}}; int hash[1000]={0}; int lenx,lenl,leng; int f[2010][2010]={{0}}; char ans1[10010]="\0"; char ans2[10010]="\0"; int ansp1=0; int ansp2=0; inline void prt(int i,int j) { if(i==0 && j==0) return; if(i>0 && j>0) if(f[i][j]==f[i-1][j-1]+cost[hash[lambda[i-1]]][hash[gama[j-1]]]) { prt(i-1,j-1); ans1[++ansp1]=lambda[i-1]; ans2[++ansp2]=gama[j-1]; return; } if(i>0) if(f[i][j]==f[i-1][j]+minl[i].mcost) { prt(i-1,j); ans1[++ansp1]=lambda[i-1]; ans2[++ansp2]=xigema[minl[i].u-1]; return; } if(j>0) if(f[i][j]==f[i][j-1]+ming[j].mcost) { prt(i,j-1); ans1[++ansp1]=xigema[ming[j].u-1]; ans2[++ansp2]=gama[j-1]; return; } return; } int main() { gets(xigema); gets(lambda); gets(gama); for(int len=strlen(xigema);xigema[len-1]=='\n' || xigema[len-1]=='\r';xigema[--len]='\0'); for(int len=strlen(lambda);lambda[len-1]=='\n' || lambda[len-1]=='\r';lambda[--len]='\0'); for(int len=strlen(gama);gama[len-1]=='\n' || gama[len-1]=='\r';gama[--len]='\0'); lenx=strlen(xigema); lenl=strlen(lambda); leng=strlen(gama); for(int i=1;i<=lenx;i++) for(int j=1;j<=lenx;j++) scanf("%d",&cost[i][j]); for(int i=1;i<=lenx;i++) hash[xigema[i-1]]=i; for(int i=1;i<=lenl;i++) { int Min=2e9,t=0; for(int j=1;j<=lenx;j++) { if(cost[hash[lambda[i-1]]][j]<Min) { t=j; Min=cost[hash[lambda[i-1]]][j]; } } minl[i].mcost=Min; minl[i].u=t; } for(int i=1;i<=leng;i++) { int Min=2e9,t=0; for(int j=1;j<=lenx;j++) { if(cost[j][hash[gama[i-1]]]<Min) { t=j; Min=cost[j][hash[gama[i-1]]]; } } ming[i].mcost=Min; ming[i].u=t; } for(int i=0;i<=lenl;i++) { for(int j=0;j<=leng;j++) { if(i==0 && j==0) continue; f[i][j]=2e9; if(i>0 && j>0) f[i][j]=f[i-1][j-1]+cost[hash[lambda[i-1]]][hash[gama[j-1]]]; if(i>0) f[i][j]=MIN(f[i][j],f[i-1][j]+minl[i].mcost); if(j>0) f[i][j]=MIN(f[i][j],f[i][j-1]+ming[j].mcost); } } printf("%d\n",f[lenl][leng]); prt(lenl,leng); puts(ans1+1); puts(ans2+1); return 0; }
sgu-214 Weird Dissimilarity
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。