LG3624 [APIO2008]DNA

· · 题解

前言

APIO 08的好题，代码量不大，思维量有一些。

解法

这种题其实套路明显，就是先预处理一些数据，最后再扫一遍求出答案。有点像二进制从高位开始一点一点逼近的感觉。

一开始，将字符串转化为数字表示。

我们可以用 DP 来求出范式-j 的个数。由题意，范式-(j-1) 也是范式-j，为了统计方便，我们先令范式-(j-1) 不是范式-j，最后前缀和合并即可。

我们令 f_{i,j,x} 为考虑到第 i 位，这一位是 x 的范式-j 个数。易得转移方程：

f_{i,j,x}=\sum\limits_{y=1}^4 f_{i+1,j-(x>y),y}

如果这一位是确定的字符，那么 x 就是一个定值。

求完前缀和后，我们按照前面所说的方法求解答案即可。

代码

有点丑（毕竟循环层数有点多）。

看了其他大佬的代码发现其实可以把代码中部分循环合并，优化常数和代码行数。但是本人较菜，觉得写这种思路清晰的代码比较好。

毕竟，你完全没必要在简单问题上耍杂技。

除非在女同学面前。

//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
    char ch=getchar();
    int f=1,x=0;
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

const int MAXN=5e4+10; 

int n,k,r;
int f[MAXN][11][5],a[MAXN];

char trans(int x) {
    if(x==1) return 'A';
    if(x==2) return 'C';
    if(x==3) return 'G';
    return 'T';
}

signed main() {
    cin>>n>>k>>r;
    for(int i=1;i<=n;i++) {
        char c;
        cin>>c;
        if(c=='A') a[i]=1;
        else if(c=='C') a[i]=2;
        else if(c=='G') a[i]=3;
        else if(c=='T') a[i]=4;
        else a[i]=0;
    }

    if(!a[n]) {
        for(int i=1;i<=4;i++) {
            f[n][1][i]=1;
        }
    }
    else {
        f[n][1][a[n]]=1;
    }

    for(int i=n-1;i;i--) {
        if(a[i]) {
            for(int j=1;j<=k;j++) {
                for(int y=1;y<=4;y++) {
                    f[i][j][a[i]]+=f[i+1][j-(a[i]>y)][y];
                }
            }
        }
        else {
            for(int x=1;x<=4;x++) {
                for(int j=1;j<=k;j++) {
                    for(int y=1;y<=4;y++) {
                        f[i][j][x]+=f[i+1][j-(x>y)][y];
                    }
                }
            }
        }
    }

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=k;j++) {
            for(int x=1;x<=4;x++) {
                f[i][j][x]+=f[i][j-1][x];
            }
        }
    }

    for(int i=1,last=0;i<=n;i++) {
        if(a[i]) {
            printf("%c",trans(a[i]));
            k-=(a[i]<last);
            last=a[i];
        }
        else {
            int x;
            for(x=1;x<=4&&r>f[i][k-(x<last)][x];x++) {
                r-=f[i][k-(x<last)][x];
            }
            printf("%c",trans(x));
            k-=(x<last);
            last=x;
        }
    }
    puts("");
    return 0;
}