4015번: DNA

https://www.acmicpc.net/problem/4015


$O(mk)$

#include<cstdio>
int m, k, s[50001];
long long r, dp[50001][11][5];
char g[] = " ACGT";
int main() {
    scanf("%d%d%lld", &m, &k, &r);
    for (int i = 0; i < m; i++) {
        char x;
        scanf(" %c", &x);
        if (x == 'A') s[i] = 1;
        if (x == 'C') s[i] = 2;
        if (x == 'G') s[i] = 3;
        if (x == 'T') s[i] = 4;
    }
    dp[m][1][4] = 1;
    for (int i = m; i--;) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= 4; l++) if (!s[i] || s[i] == l) {
                for (int n = 1; n < l; n++) dp[i][j][l] += dp[i + 1][j - 1][n];
                for (int n = l; n <= 4; n++) dp[i][j][l] += dp[i + 1][j][n];
            }
        }
    }
    for (int i = m; i--;)
        for (int j = 1; j <= k; j++)
            for (int l = 1; l <= 4; l++) dp[i][j][l] += dp[i][j - 1][l];
    for (int i = 0; i < m; i++) {
        if (s[i]) putchar(g[s[i]]);
        else {
            for (int j = 1; j <= 4; j++) {
                int t = 0;
                if (i&&s[i - 1]>j) t = 1;
                if (dp[i][k - t][j] < r) r -= dp[i][k - t][j];
                else {
                    s[i] = j;
                    putchar(g[j]);
                    break;
                }
            }
        }
        if (i&&s[i - 1] > s[i]) k--;
    }
    return 0;
}