语文很重要!!! 如果题目意思都不理解, 怎么可能写出正解?! 两个序列都可以插空位! 两个序列都可以插空位! 两个序列都可以插空位!
其实如果写过最长公共子序列, 这道题简直就是水题 (考察阅读理解). 在这里放一波最长公共子序列, 对于序列 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 数组初始化等细节需要处理好.
- #include<cstdio>
- using namespace std;
- const int maxn=105;
- const int de[5][5]={
- {5,-1,-2,-1,-3},
- {-1,5,-3,-2,-4},
- {-2,-3,5,-2,-2},
- {-1,-2,-2,5,-1},
- {-3,-4,-2,-1,-0x3f3f3f3f}
- };
- int n1,n2,dp[maxn][maxn];
- char s1[maxn],s2[maxn];
- inline int max(int a,int b) {return a>b?a:b;}
- int toint(char c) {
- if(c=='A') return 0;
- else if(c=='C') return 1;
- else if(c=='G') return 2;
- else if(c=='T') return 3;
- else return 4;
- }
- int degree(char a,char b) {
- return de[toint(a)][toint(b)];
- }
- int main() {
- scanf("%d",&n1);scanf("%s",s1+1);
- scanf("%d",&n2);scanf("%s",s2+1);
- for(int i=1;i<=n1;++i) dp[i][0]=degree(s1[i],'-')+dp[i-1][0];
- for(int i=1;i<=n2;++i) dp[0][i]=degree(s2[i],'-')+dp[0][i-1];
- for(int i=1;i<=n1;++i)
- for(int j=1;j<=n2;++j) {
- dp[i][j]=dp[i-1][j-1]+degree(s1[i],s2[j]);
- dp[i][j]=max(dp[i][j],dp[i-1][j]+degree(s1[i],'-'));
- dp[i][j]=max(dp[i][j],dp[i][j-1]+degree(s2[j],'-'));
- }
- printf("%d",dp[n1][n2]);
- return 0;
- }
AC 代码
[洛谷习题]相似基因
来源: http://www.bubuko.com/infodetail-2759540.html