LibreOJ 2575 「TJOI2018」游园会

发表于 | 分类于 | 9

DP 套 DP 还是蛮有趣的（

可以先不考虑不含 NOI 子串的限制。（这时其实是个丽洁姐的原题）
注意到 LCS 不太方便用状态表示，于是可以考虑造一个 LCS 自动机。

考虑传统的 O(|A||B|) 求串 A,B LCS 的 DP 方法： fi,j=max{fi−1,j,fi,j−1,fi−1,j−1+[Ai=Bj]}

注意到这个 DP 仅涉及到两个串的上一个字符，并且此题中有一个串是固定的，那么可以把另一个串对应的维度看做一个自动机上的结点。
麻烦的是，空间会很大，而且难以得出结点数的上界。

再次考虑 f 的定义，容易发现数组 fi 的差分数组一定非 0 即 1，所以可以考虑状压（K≤15）。
这样就会得到一个比较松但是足够用的上界，即 215。
（经实测本题数据中最多的结点数不超过 5000）
然后 BFS 建自动机即可。

解决了自动机的问题之后，考虑设 gi,j 表示兑奖串的前 i 位能走到自动机上的结点 j 的方案数。
那么转移时仅需要枚举新的字符并走后缀自动机上的边即可。

然后涉及到不含 NOI 子串的限制。
——实际上也很简单，只需要新增一维表示当前后缀和 NOI 的最长匹配长度。

此外，由于此题时限较宽裕，所以也可以不显式建出自动机而是在转移 g 时直接转移 f。
（这样就要按照状压的方式来存储结点）
然后这其实就是 DP 套 DP 的名字来源（

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e3;
const int K = 15;
const int M = 5e3;
const int mod = 1e9 + 7;
int n,k,s[K + 5];
inline int trans(int w,int c)
{
    static int a[K + 5],f[K + 5];
    int ret = 0;
    for(register int i = 1;i <= k;++i)
        a[i] = a[i - 1] + ((w >> i - 1) & 1);
    for(register int i = 1;i <= k;++i)
        f[i] = max(max(a[i],f[i - 1]),a[i - 1] + (s[i] == c)),
        ret |= f[i] - f[i - 1] << i - 1;
    return ret;
}
int q[M + 5];
int head,tail;
int tot,e[M + 5][3],id[(1 << K) + 5],rk[(1 << K) + 5];
inline void bfs()
{
    rk[id[q[++tail] = 0] = ++tot] = 0;
    for(register int p,dir,x;head < tail;)
    {
        p = q[++head],x = id[p];
        for(register int i = 0;i < 3;++i)
        {
            dir = trans(p,i);
            if(id[dir])
                e[x][i] = id[dir];
            else
                rk[e[x][i] = id[dir] = ++tot] = q[++tail] = dir;
        }
    }
}
int f[2][M + 5][3],ans[K + 5];
int main()
{
    scanf("%d%d",&n,&k);
    char ch;
    for(register int i = 1;i <= k;++i)
        scanf(" %c",&ch),s[i] = ch == 'I' ? 2 : ch == 'O';
    bfs(),f[0][1][0] = 1;
    for(register int i = 0;i < n;++i)
    {
        memset(f[(i & 1) ^ 1],0,sizeof f[(i & 1) ^ 1]);
        for(register int j = 1;j <= tot;++j)
        {
            if(f[i & 1][j][0])
                f[(i & 1) ^ 1][e[j][0]][1] = (f[(i & 1) ^ 1][e[j][0]][1] + f[i & 1][j][0]) % mod,
                f[(i & 1) ^ 1][e[j][1]][0] = (f[(i & 1) ^ 1][e[j][1]][0] + f[i & 1][j][0]) % mod,
                f[(i & 1) ^ 1][e[j][2]][0] = (f[(i & 1) ^ 1][e[j][2]][0] + f[i & 1][j][0]) % mod;
            if(f[i & 1][j][1])
                f[(i & 1) ^ 1][e[j][0]][1] = (f[(i & 1) ^ 1][e[j][0]][1] + f[i & 1][j][1]) % mod,
                f[(i & 1) ^ 1][e[j][1]][2] = (f[(i & 1) ^ 1][e[j][1]][2] + f[i & 1][j][1]) % mod,
                f[(i & 1) ^ 1][e[j][2]][0] = (f[(i & 1) ^ 1][e[j][2]][0] + f[i & 1][j][1]) % mod;
            if(f[i & 1][j][2])
                f[(i & 1) ^ 1][e[j][0]][1] = (f[(i & 1) ^ 1][e[j][0]][1] + f[i & 1][j][2]) % mod,
                f[(i & 1) ^ 1][e[j][1]][0] = (f[(i & 1) ^ 1][e[j][1]][0] + f[i & 1][j][2]) % mod;
        }
    }
    for(register int i = 1;i <= tot;++i)
        for(register int j = 0;j < 3;++j)
            ans[__builtin_popcount(rk[i])] = (ans[__builtin_popcount(rk[i])] + f[n & 1][i][j]) % mod;
    for(register int i = 0;i <= k;++i)
        printf("%d\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment