BZOJ4416: [Shoi2013]阶乘字符串

可以大胆猜想n>21时无解，至于依据，不开O2，1s，n<=21刚好能卡过去= =

并不会证= =

#include<cstdio>void up(int& a,int b){a=a<b?b:a;}int test,n,m,i,j;char t[500];int f[1<<21],s[500][21];int main(){scanf("%d",&test);while(test--){scanf("%d%s",&n,t);if(n>21)puts("NO");if(n>21)continue;for(m=0;t[m];++m)t[m]-=97;for(j=0;j<n;++j)s[m+1][j]=s[m][j]=m+1;for(i=m-1;~i;--i)for(j=0;j<n;++j)s[i][j]=j==t[i]?i+1:s[i+1][j];for(i=1;i<1<<n;++i)for(f[i]=j=0;j<n;++j)if(i&1<<j)up(f[i],s[f[i^1<<j]][j]);puts(f[~(~0<<n)]<=m?"YES":"NO");}}