「CodePlus 2017 11 月赛」找爸爸

题意简述

给两个仅含

A,T,C,G

的字符串，以及其两两匹配对答案产生的贡献，可以在两个字符串中间任意插空格，一段长为

k

的空格对答案产生的贡献是

A-B*(k-1)

（

A,B

给定），也就是一段空格，第一个空格产生的贡献是

-A

，第二个及更多是

-B

。求两个字符串能构造出来的最大贡献。

思路

直接 DP。设

f_{i, j, 1/0, 1/0}

是

s_1

选到

i

，

s_2

选到

j

，并且当前

s_1,s_2

这一位分别是数字 / 空格的最大答案。那么状态转移方程就可以写出来了：

f_{i,j,1,1}=\begin{cases} f_{i-1,j-1,1,0} + w_{s1_i, s2_j}\\ f_{i-1,j-1,0,1} + w_{s1_i, s2_j}\\ f_{i-1,j-1,1,1} + w_{s1_i, s2_j} \end{cases}\\ f_{i,j,1,0}=\begin{cases} f_{i-1,j,1,0} - B\\ f_{i-1,j,0,1} - A\\ f_{i-1,j,1,1} - A \end{cases}\\ f_{i,j,0,1}=\begin{cases} f_{i,j-1,0,1} - B\\ f_{i,j-1,1,0} - A\\ f_{i,j-1,1,1} - A \end{cases}\\

转移时取 max 就可以了。本题主要吃代码细节。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

inline ll read(){
	ll res = 0, f = 1;
	char c = getchar();
	while(c > '9' || c < '0'){
		if(c == '-')f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		res = res * 10 + c - '0';
		c = getchar();
	}
	return res * f;
}

const int N = 4010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll w[10][10], f[N][N][2][2];
int a[N], b[N];

signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	ll n = s1. size(), m = s2. size();
	s1 = ' ' + s1, s2 = ' ' + s2;
	for(int i = 1; i <= n; i ++){
		switch(s1[i]){
			case 'A':
				a[i] = 1;
				break;
			case 'T':
				a[i] = 2;
				break;
			case 'G':
				a[i] = 3;
				break;
			case 'C':
				a[i] = 4;
				break;
		}
	}
	for(int i = 1; i <= m; i ++){
		switch(s2[i]){
			case 'A':
				b[i] = 1;
				break;
			case 'T':
				b[i] = 2;
				break;
			case 'G':
				b[i] = 3;
				break;
			case 'C':
				b[i] = 4;
				break;
		}
	}
	for(int i = 1; i <= 4; i ++){
		for(int j = 1; j <= 4; j ++){
			w[i][j] = read();
		}
	}
	ll A = read(), B = read();
	ll len = max(n, m);
	memset(f, -0x3f, sizeof f);
	f[0][0][0][0] = 0;
    for(int i = 1; i <= n ; i ++){
        f[i][0][1][0] = f[i - 1][0][0][0] - A;
        f[0][i][0][1] = f[0][i - 1][0][0] - A;
        f[i][0][1][0] = max(f[i][0][1][0], f[i - 1][0][1][0] - B);
        f[0][i][0][1] = max(f[0][i][0][1], f[0][i - 1][0][1] - B);

    }
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			f[i][j][1][1] = max(f[i][j][1][1], f[i - 1][j - 1][0][0] + w[a[i]][b[j]]);
			f[i][j][1][1] = max(f[i][j][1][1], f[i - 1][j - 1][1][0] + w[a[i]][b[j]]);
			f[i][j][1][1] = max(f[i][j][1][1], f[i - 1][j - 1][0][1] + w[a[i]][b[j]]);
			f[i][j][1][1] = max(f[i][j][1][1], f[i - 1][j - 1][1][1] + w[a[i]][b[j]]);


			f[i][j][0][1] = max(f[i][j][0][1], f[i][j - 1][0][1] - B);
			f[i][j][0][1] = max(f[i][j][0][1], f[i][j - 1][1][0] - A);
			f[i][j][0][1] = max(f[i][j][0][1], f[i][j - 1][1][1] - A);


			f[i][j][1][0] = max(f[i][j][1][0], f[i - 1][j][1][0] - B);
			f[i][j][1][0] = max(f[i][j][1][0], f[i - 1][j][0][1] - A);
			f[i][j][1][0] = max(f[i][j][1][0], f[i - 1][j][1][1] - A);
			
			// cout << i << ' ' << j << " " << f[i][j][0][1] << " " << f[i][j][1][0] << " " << f[i][j][1][1] << endl;  
		}       
	}
	ll ans = -INF;
	ans = max(ans, f[n][m][0][1]);
	ans = max(ans, f[n][m][1][0]);
	ans = max(ans, f[n][m][1][1]);
	cout << ans;
	return 0;
}

「CodePlus 2017 11 月赛」找爸爸

文章操作

题意简述

思路

代码

相关推荐

评论

「CodePlus 2017 11 月赛」找爸爸