BZOJ 4416 「SHOI2013」阶乘字符串

发表于 | 分类于 |

根据 Claris 之语，合法的字符串长度在 \(n^2\) 左右，所以当 \(n > 21\) 时直接判否。

然后考虑状压 DP。
首先求出一个辅助数组 \(nxt_{i,j}\) 表示使得 \(S_k = j,k > i\) 的最小的 \(k\)。
然后考虑设 \(f_s\) 表示使得 \(S_{1,k}\) 满足字符集合 \(s\) 的阶乘字符串的最小的 \(k\)。

转移直接枚举新的字符，然后借助 \(nxt\) 转移即可。
注意处理 \(nxt\) 的时候要考虑大于 \(|S|\) 的情况，小心炸掉。

代码： 

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 450;
const int MX = 21;
int T,n,len,full;
char s[N + 5];
int f[(1 << MX) + 5],nxt[N + 5][30];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%s",&n,s + 1);
        if(n > 21)
        {
            puts("NO");
            continue;
        }
        len = strlen(s + 1),full = (1 << n) - 1;
        memset(f,0,sizeof f),memset(nxt,0,sizeof nxt);
        for(register int i = 1;i <= n;++i)
            nxt[len][i] = nxt[len + 1][i] = len + 1;
        for(register int i = len;i;--i)
        {
            for(register int j = 1;j <= n;++j)
                nxt[i - 1][j] = nxt[i][j];
            nxt[i - 1][s[i] - 'a' + 1] = i;
        }
        for(register int i = 0;i <= full;++i)
            for(register int j = 1;j <= n;++j)
                if(!(i & (1 << j - 1)))
                    f[i | (1 << j - 1)] = max(f[i | (1 << j - 1)],nxt[f[i]][j]);
        puts(f[full] <= len ? "YES" : "NO");
    }
}