BZOJ 4416 「SHOI2013」阶乘字符串

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

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

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

代码：

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