首页 > 其他 > 详细

BZOJ4416 : [Shoi2013]阶乘字符串

时间:2016-03-06 22:06:00      阅读:257      评论:0      收藏:0      [点我收藏+]

最小的合法串长是$O(n^2)$级别,所以当$n>21$时无解。

设$g[i][j]$为$i$后面第一个字符$j$的位置,没有就是$m+1$。

设$f[S]$为之前序列的集合为$S$,全员匹配到的最早可行位置,然后枚举最后一位进行转移,若$f[(1<<n)-1]\leq m$则可行。

时间复杂度$O(nm+n2^n)$。

 

#include<cstdio>
#include<cstring>
int T,n,m,i,j,k,t,g[500][26];char a[500];short f[1<<21];
inline void up(int x){if(x>t)t=x;}
int main(){
  scanf("%d",&T);
  while(T--){
    scanf("%d%s",&n,a+1);m=strlen(a+1);
    if(n>21){puts("NO");continue;}
    for(j=0;j<n;j++)g[m][j]=g[m+1][j]=m+1;
    for(i=m;i;i--){
      for(j=0;j<n;j++)g[i-1][j]=g[i][j];
      g[i-1][a[i]-‘a‘]=i;
    }
    for(i=1;i<1<<n;i++){
      for(t=0,j=i;j;j-=j&-j)k=__builtin_ctz(j),up(g[f[i^(1<<k)]][k]);
      f[i]=t;
    }
    puts(f[(1<<n)-1]>m?"NO":"YES");
  }
  return 0;
}

  

BZOJ4416 : [Shoi2013]阶乘字符串

原文:http://www.cnblogs.com/clrs97/p/5248729.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!