欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1140 相似基因(简单dp)

程序员文章站 2022-07-13 12:06:55
...

题目来源

https://www.luogu.com.cn/problem/P1140

题面

P1140 相似基因(简单dp)

题意

给定权值匹配表,求最大一个匹配顺序的匹配权值最大。

思路

  • dp[i][j]aibjdp[i][j]表示a的前i个和b的前j个相匹配的最大值
  • dp[i][j]=max(dp[i1][j1]+(a[i]b[j]),dp[i1][j]+(a[i]),dp[i][j1]+(b[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]与空的匹配值)

参考代码

#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;
}