「CodePlus 2017 11 月赛」找爸爸

Rt__ · 2024-11-25 12:00:07 · 题解

「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 这一位分别是数字 / 空格的最大答案。那么状态转移方程就可以写出来了：

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

代码

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