BZOJ 4416: [Shoi2013]阶乘字符串

简单的状压DP，而且很困惑为什么大家都不知道判无解的原因？

首先有一个结论，当\(n>21\)时无解，证明如下（个人口胡不保证正确性）：

考虑当我们的字符串是这样构造时：一个\(n\)个字符的排列+一个\(n\)个字符的排列+……+一个\(n\)个字符的排列（共计\(n\)个），此时显然是有解的

再手玩一下容易发现这个条件不仅充分而且必要，如果有一段中间有字符缺失那么必然会导致某个排列无法表示出来

那么很显然最优的表示方案就是类似分块的根号级别的分组，由\(\sqrt{450}=21.2\cdots\)，因此超过\(21\)无解

剩下的非常简单了，排列化为子集，设\(f_{s}\)表示集合\(s\)（状压）内的字符都满足要求是右端点至少到那里

转移考虑分别讨论\(s\)的最后一个字符是什么，那么：

\[f_s=\max\{ g_{f_{s\cap C_s c},c}|c\in s\}\]

其中\(g_{i,j}\)表示在位置\(i\)之后（不包含）第一个\(j\)的位置，取\(\max\)是因为对于任意一个字符都要满足

最后判断一下\(f_{\text{全集}}\)与\(len\)的关系即可

#include<cstdio>
#include<cstring>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=455;
int t,n,len,f[1<<21],g[N][21],lim; char s[N];
int main()
{
    for (scanf("%d",&t);t;--t)
    {
        scanf("%d%s",&n,s+1); len=strlen(s+1);
        if (n>21) { puts("NO"); continue; }
        RI i,j; for (i=0;i<n;++i) g[len][i]=g[len+1][i]=len+1;
        for (i=len-1;~i;--i) for (j=0;j<n;++j)
        g[i][j]=s[i+1]==j+'a'?i+1:g[i+1][j];
        for (lim=1<<n,i=0;i<lim;++i) for (f[i]=j=0;j<n;++j)
        if (i&(1<<j)) f[i]=max(f[i],g[f[i^(1<<j)]][j]);
        puts(f[lim-1]==len+1?"NO":"YES");
    }
    return 0;
}

BZOJ 4416: [Shoi2013]阶乘字符串

原文：https://www.cnblogs.com/cjjsb/p/12241381.html