bzoj 4606: [Apio2008]DNA

题意：

给你一个包含通配符的DNA序列，对每个碱基定义一个优先级$A > C > G > T$。定义：如果一个DNA序列是范式-1的，那么它每个碱基要么和它右边的碱基相同，要么比它右边的碱基优先级高；如果一个DNA序列是范式-k的，那么它要么属于范式-(k - 1)，要么是一个属于范式-(k - 1)和一个范式-1的连接。往通配符里填碱基，使它属于范式-k，找出这中间字典序排第$r$的。

题解：

这次是看错数据范围。。。看多了一个0。。。然后就MLE了。。。
这个范式其实就是$a_i < a_{i + 1}$的个数$ + 1$。设$f_{i, j, k}$表示$i$到$n$，$a_i = j$，已经有$k$个$a_i < a_{i + 1}$的方案数。倒着求$f$，然后正着找到第$r$个就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

int m, k, a[50010], ans[50010];
long long r, f[50010][4][10];
char s[50010];

int main()
{
    scanf("%d%d%lld%s", &m, &k, &r, s + 1);
    for (int i = 1; i <= m; i++)
    {
        if (s[i] == 'A') a[i] = 3;
        else if (s[i] == 'C') a[i] = 2;
        else if (s[i] == 'G') a[i] = 1;
        else if (s[i] == 'T') a[i] = 0;
        else a[i] = -1;
    }/*
    for (int i = 1; i <= m; i++)
        printf("%d ", a[i]);
    puts("");*/
    if (~a[m]) f[m][a[m]][0] = 1;
    else f[m][0][0] = f[m][1][0] = f[m][2][0] = f[m][3][0] = 1;
    for (int i = m - 1; i > 0; i--)
        for (int j = 0; j < k; j++)
        {
            if (~a[i])
            {
                for (int l = a[i]; l >= 0; l--)
                    f[i][a[i]][j] += f[i + 1][l][j];
                if (j)
                    for (int l = a[i] + 1; l < 4; l++)
                        f[i][a[i]][j] += f[i + 1][l][j - 1];
            }
            else
            {
                // printf("i: %d j: %d\n", i, j);
                for (a[i] = 0; a[i] < 4; a[i]++)
                {
                    for (int l = a[i]; l >= 0; l--)
                        f[i][a[i]][j] += f[i + 1][l][j];
                    if (j)
                    {
                        // puts("a");
                        for (int l = a[i] + 1; l < 4; l++)
                            f[i][a[i]][j] += f[i + 1][l][j - 1];
                    }
                }
                a[i] = -1;
            }
        }/*
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            for (int l = 0; l < k; l++)
                printf("%lld ", f[i][j][l]);
            puts("");
        }
        puts("");
    }*/
    ans[0] = 3;
    int used = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 3; j >= 0; j--)
        {
            int mx = k - used - (j > ans[i - 1]);
            long long hh = 0;
            for (int l = 0; l < mx; l++)
                hh += f[i][j][l];
            if (hh < r)
                r -= hh;
            else
            {
                ans[i] = j;
                used += j > ans[i - 1];
                break;
            }
        }
    }
    for (int i = 1; i <= m; i++)
        if (ans[i] == 3) putchar('A');
        else if (ans[i] == 2) putchar('C');
        else if (ans[i] == 1) putchar('G');
        else putchar('T');
    puts("");
}