description

给定一个由前n个小写字母组成的串S。

串S是阶乘字符串当且仅当前n个小写字母的全排列（共n!种）都作为S的子序列（可以不连续）出现。

由这个定义出发，可以得到一个简单的枚举法去验证，但是它实在太慢了。所以现在请你设计一个算法，在1秒内判断出给定的串是否是阶乘字符串。

analysis

• 状压\(DP\)

• 不知道为什么\(22\)个字母或以上的都不合法

• 设\(f[S]\)表示\(S\)状态中为\(1\)的字母的全排列全都出现过的最前位置

• 转移就是在某个全排列的末尾插上一个新字母，枚举新字母转移

• 先预处理出每个位置到某下一字母的最前位置，就可以容易地\(DP\)了

code

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 2100000
#define INF 1000000007
#define ll long long
#define fo(i,a,b) for (ll i=a;i<=b;++i)
#define fd(i,a,b) for (ll i=a;i>=b;--i)

using namespace std;

ll f[MAXN];
ll g[500][26];
char st[500];
ll n,T,len;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline ll max(ll x,ll y){return x>y?x:y;}
int main()
{
    freopen("T2.in","r",stdin);
    T=read();
    while (T--)
    {
        n=read(),scanf("\n%s",st+1);
        if (n>21){printf("NO\n");continue;}
        len=strlen(st+1);
        fo(i,0,n-1)g[len][i]=g[len+1][i]=len+1;
        fd(i,len-1,0)
        {
            fo(j,0,n-1)g[i][j]=g[i+1][j];
            g[i][st[i+1]-'a']=i+1;
        }
        memset(f,0,sizeof(f));
        fo(status,1,(1<<n)-1)
        {
            fo(i,0,n-1)if (status&(1<<i))
            f[status]=max(f[status],g[f[status^(1<<i)]][i]);
        }
        printf(f[(1<<n)-1]==len+1?"NO\n":"YES\n");
    }
    return 0;
}

【JZOJ3293】阶乘字符串

原文：https://www.cnblogs.com/horizonwd/p/11121298.html