P1140 相似基因(简单dp)
程序员文章站
2022-07-13 12:06:55
...
题目来源
https://www.luogu.com.cn/problem/P1140
题面
题意
给定权值匹配表,求最大一个匹配顺序的匹配权值最大。
思路
参考代码
#include <iostream>
using namespace std;
const ll N = 1e3 + 5;
const int mmp[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,0}
};
int n,m,a[N],b[N],dp[N][N];//a[i]和b[i]起到map的作用,dp[i][j]表示a的前i个和b的前j个相匹配的最大值
int main() {
cin >> n ;
for(int i = 1 ; i <= n ; i++) {
char s ;
cin >> s ;
if(s == 'A') {
a[i] = 0 ;
} else if(s == 'C') {
a[i] = 1 ;
} else if(s == 'G') {
a[i] = 2 ;
} else {
a[i] = 3 ;
}
}
cin >> m ;
for(int i = 1 ; i <= m ; i++) {
char s ;
cin >> s ;
if(s == 'A') {
b[i] = 0 ;
} else if(s == 'C') {
b[i] = 1 ;
} else if(s == 'G') {
b[i] = 2 ;
} else {
b[i] = 3 ;
}
}
int temp = 0 ;
for(int i = 0 ; i <= m ; i++) {//预处理dp边界,当一个序列长度为0时,就是相当于另一个序列全部和"-"对应
dp[0][i] = temp;
temp += mmp[b[i+1]][4] ;
}
temp = 0 ;
for(int i = 0 ; i <= n ; i++) {//同理
dp[i][0] = temp ;
temp += mmp[a[i+1]][4] ;
}
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= m ; j++) {
//dp[i][j]=max(dp[i-1][j-1]+(a[i]与b[j]的匹配值),dp[i-1][j]+(a[i]与空的匹配值),dp[i][j-1]+(b[j]与空的匹配值);
dp[i][j] = max(dp[i-1][j-1] + mmp[a[i]][b[j]] , max(dp[i-1][j] + mmp[a[i]][4] , dp[i][j-1] + mmp[b[j]][4])) ;
}
}
cout << dp[n][m] << endl;//输出答案
return 0;
}