怎么也没想到是子集DP，想到了应该就没什么难度了。
首先n>21时必定为NO。
g[i][j]表示位置i后的第一个字母j在哪个位置，n*21求出。
f[S]表示S的所有全排列子序列出现的最后末尾位置，枚举最后一个字母转移。21*2^21
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 using namespace std; 6 7 int T,n,m,k,t,g[500][26],f[1<<21]; 8 char a[500]; 9 10 int main(){ 11 freopen("bzoj4416.in","r",stdin); 12 freopen("bzoj4416.out","w",stdout); 13 scanf("%d",&T); 14 while(T--){ 15 scanf("%d%s",&n,a+1); m=strlen(a+1); 16 if (n>21){ puts("NO"); continue; } 17 rep(j,0,n-1) g[m][j]=g[m+1][j]=m+1; 18 for(int i=m; i; i--){ 19 rep(j,0,n-1) g[i-1][j]=g[i][j]; 20 g[i-1][a[i]-'a']=i; 21 } 22 rep(i,1,(1<<n)-1){ 23 int res=0; 24 for(int j=i; j; j-=j&-j) 25 k=__builtin_ctz(j),res=max(res,g[f[i^(1<<k)]][k]);//ctz统计末尾0的个数 26 f[i]=res; 27 } 28 puts(f[(1<<n)-1]>m ? "NO" : "YES"); 29 } 30 return 0; 31 }