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");
}
}