[数据结构与算法]P1140 相似基因(线性dp)

P1140?相似基因https://www.luogu.com.cn/problem/P1140????????写完这一题之后感觉自己进步了哈哈哈

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
#include <cstdlib>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 2000010;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)

int nec[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, INF}};
int dp[105][105];
char s1[MAXN], s2[MAXN];
int n1, n2;
map<char, int> mp;

int main() {
	mp['A'] = 0;
	mp['C'] = 1;
	mp['G'] = 2;
	mp['T'] = 3;
	mp['-'] = 4;
	scanf("%d", &n1);
	for (int i = 1; i <= n1; i++) {
		scanf(" %c", s1 + i);
	}
	scanf("%d", &n2);
	for (int i = 1; i <= n2; i++) {
		scanf(" %c", s2 + i);
	}
	for (int i = 1; i <= n1; i++) {
		dp[i][0] = dp[i - 1][0] + nec[mp[s1[i]]][4];
	}
	for (int i = 1; i <= n2; i++) {
		dp[0][i] = dp[0][i - 1] + nec[4][mp[s2[i]]];
	}
	for (int i = 1; i <= n1; i++) {
		for (int j = 1; j <= n2; j++) {
			dp[i][j] = max(max(dp[i - 1][j] + nec[mp[s1[i]]][4], dp[i][j - 1] + nec[4][mp[s2[j]]]),
			               dp[i - 1][j - 1] + nec[mp[s1[i]]][mp[s2[j]]]);
		}
	}
	printf("%d", dp[n1][n2]);
	return 0;
}