题目链接:https://www.luogu.org/problemnew/show/P1140
语文很重要!!!如果题目意思都不理解,怎么可能写出正解?!两个序列都可以插空位!两个序列都可以插空位!两个序列都可以插空位!
其实如果写过最长公共子序列,这道题简直就是水题(考察阅读理解)。在这里放一波最长公共子序列,对于序列s1,s2,我们定义dp[i][j]表示考虑到s1的第i个元素,s2的第j个元素所能取到的最长公共子序列的长度,枚举i,j,若s1[i]=s2[j],则他们可以作为最长公共子序列的结尾,dp[i][j]=dp[i-1][j-1]+1;反之,s[i]和s[j]不可以作为最长公共子序列的结尾,dp[i][j]=max(dp[i][j-1],dp[i-1][j])。
本题同理,只不过字符的转换、dp数组初始化等细节需要处理好。
1 #include<cstdio> 2 using namespace std; 3 const int maxn=105; 4 const int de[5][5]={ 5 {5,-1,-2,-1,-3}, 6 {-1,5,-3,-2,-4}, 7 {-2,-3,5,-2,-2}, 8 {-1,-2,-2,5,-1}, 9 {-3,-4,-2,-1,-0x3f3f3f3f} 10 }; 11 int n1,n2,dp[maxn][maxn]; 12 char s1[maxn],s2[maxn]; 13 inline int max(int a,int b) {return a>b?a:b;} 14 int toint(char c) { 15 if(c==‘A‘) return 0; 16 else if(c==‘C‘) return 1; 17 else if(c==‘G‘) return 2; 18 else if(c==‘T‘) return 3; 19 else return 4; 20 } 21 int degree(char a,char b) { 22 return de[toint(a)][toint(b)]; 23 } 24 int main() { 25 scanf("%d",&n1);scanf("%s",s1+1); 26 scanf("%d",&n2);scanf("%s",s2+1); 27 for(int i=1;i<=n1;++i) dp[i][0]=degree(s1[i],‘-‘)+dp[i-1][0]; 28 for(int i=1;i<=n2;++i) dp[0][i]=degree(s2[i],‘-‘)+dp[0][i-1]; 29 for(int i=1;i<=n1;++i) 30 for(int j=1;j<=n2;++j) { 31 dp[i][j]=dp[i-1][j-1]+degree(s1[i],s2[j]); 32 dp[i][j]=max(dp[i][j],dp[i-1][j]+degree(s1[i],‘-‘)); 33 dp[i][j]=max(dp[i][j],dp[i][j-1]+degree(s2[j],‘-‘)); 34 } 35 printf("%d",dp[n1][n2]); 36 return 0; 37 }
原文:https://www.cnblogs.com/Mr94Kevin/p/9607579.html