BZOJ 4416.「SHOI2013」阶乘字符串

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

然后考虑状压 DP。
首先求出一个辅助数组 nxti,jnxt_{i,j} 表示使得 Sk=j,k>iS_k = j,k > i 的最小的 kk
然后考虑设 fsf_s 表示使得 S1,kS_{1,k} 满足字符集合 ss 的阶乘字符串的最小的 kk

转移直接枚举新的字符,然后借助 nxtnxt 转移即可。
注意处理 nxtnxt 的时候要考虑大于 S|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");
}
}