20pts, 无前人的错误,求调
查看原帖
20pts, 无前人的错误,求调
1074348
mumuxiao20111101楼主2024/12/11 15:49
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T> inline void read(T & x) {
	x = 0;
	int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
template <typename T> void print(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}
char xa[100005], xb[100005];
int n;
int m;
int d[10][10];
int f[3005][3005][3];
int x[1000005];
int y[1000005];
signed main() {
	cin >> xa >> xb;
	int lena = strlen(xa);
	int lenb = strlen(xb);
	for (int i = 1; i <= 4; i++){
		for (int j = 1; j <= 4; j++){
			read(d[i][j]);
		}
	}
	read(n);
	read(m);
	for (int i = 1; i <= lena; i ++){
		if (xa[i - 1] == 'A') x[i] = 1;
		else if (xa[i - 1] == 'T') x[i] = 2;
		else if (xa[i - 1] == 'G') x[i] = 3;
		else x[i] = 4;
	}
	for (int i = 1; i <= lenb; i ++){
		if (xb[i - 1] == 'A') y[i] = 1;
		else if (xb[i - 1] == 'T') y[i] = 2;
		else if (xb[i - 1] == 'G') y[i] = 3;
		else y[i] = 4;
	}
	for (int i = max(lena, lenb); i; --i ) {
		f[0][i][0] = -(1LL << 60); 
		f[i][0][0] = -(1LL << 60); 
		f[0][i][2] = -(1LL << 60); 
		f[i][0][1] = -(1LL << 60);
		f[0][i][1] = - lena - lenb * (i - 1);
		f[i][0][2] = - lena - lenb * (i - 1);
	}
	f[0][0][1] = -(1LL << 60);
	f[0][0][2] = -(1LL << 60);
	for (int i = 1; i <= lena; i ++){
		for (int j = 1; j <= lenb; j ++) {
			f[i][j][0] = max({f[i - 1][j - 1][0], f[i - 1][j - 1][1], f[i - 1][j - 1][2]}) + d[x[i]][y[j]];
			f[i][j][1] = max({f[i][j - 1][1] - m, f[i][j - 1][0] - n, f[i][j - 1][2] - n});
			f[i][j][2] = max({f[i - 1][j][2] - m, f[i][j - 1][0] - n, f[i - 1][j][1] - n});
		}
	}
	print(max({f[lena][lenb][0], f[lena][lenb][1], f[lena][lenb][2]}));	
}
2024/12/11 15:49
加载中...