题目链接：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
