[Codeforces 696D] Legen...

　　题目大意：

　　　　给出一些匹配串，要造一个长度不超过L的字符串，每个匹配串有自己的价值，匹配串每次出现在字符串里都会贡献一次价值...要求可能得到的最大价值。

　　　　匹配串总长不超200，L<=10^14，时限6s

　　典型的倍增floyd...看数据范围大概就知道是什么东西了= =

　　暴力写法的话..建个AC自动机，每个节点的价值，就是结束节点在它的fail链上的匹配串的价值总和。。然后在上面暴力DP。f[i][j]表示从i节点开始，往后走j步能得到的最大价值。

　　这个形式和USACO那道“奶牛接力跑‘一模一样。。。

　　f[i][j][k]表示从i节点开始，走2^j步，到达k的最大价值。fa[i][j][k]:从k节点开始，走2^j步，能否到达i。

　　f[i][j][k]=max{ f[i][j-1][k1]+f[k1][j-1][k] }，（ fa[k1][j-1][i]和fa[k][j-1][k1]为true

　　求出f后，就和快速幂的姿势一样把L拆成若干个二的次幂之和，然后把对应的各个f数组并起来（记为g）。

　　最后的答案就是max{ g[0][i] }，（i为自动机上的节点。

　　时间复杂度O（n^3*logL）..CF测评姬挺快的。。只跑了1200+ms。。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<bitset>

 #define ll long long

 #define ull unsigned long long

 #define d double

 using namespace std;

 const int maxn=;

 const ll inf=(1ll<<)-1ll;

 int ch[maxn][],next[maxn][],tot;

 int dl[maxn],fail[maxn],val[maxn],v[maxn];

 ll f[maxn][][maxn],g[maxn][][maxn];

 bitset<maxn>fa[maxn][];

 char s[maxn];

 int i,j,k,n,m,now,pre;

 ll L;

 bool first=;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while(rx!='-'&&(rx<''||rx>''))rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;

 }

 inline void upd(ll &a,ll b){if(a<b)a=b;}

 void trie(int n,int v){

     int p=;

     for(int i=;i<=n;i++){

         s[i]-='a';

         if(!ch[p][s[i]])ch[p][s[i]]=++tot,p=tot;

         else p=ch[p][s[i]];

     }

     val[p]+=v;//printf("   ggpos:%d\n",p);

 }

 void getfail(){

     int l=,r=,i,now,j,p;dl[]=;

     while(l<r){

         now=dl[++l];

         for(i=;i<;i++)if(ch[now][i]){

             j=ch[now][i],dl[++r]=j,next[now][i]=j;

             for(p=fail[now];p&&!ch[p][i];p=fail[p]);

             if(!now)fail[j]=;else fail[j]=ch[p][i];

             val[j]+=val[fail[j]];//printf("   %d - - - ->%d   val:%d\n",j,fail[j],val[j]);

         }else{

             for(p=fail[now];p&&!ch[p][i];p=fail[p]);

             next[now][i]=ch[p][i];

         }

     }

 }

 inline void run_fa(int j){

     int i,k1;//printf("j:%d\n",j);

     for(i=;i<=tot;i++)for(k1=;k1<=tot;k1++)

         if(fa[i][j-][k1])fa[i][j]|=fa[k1][j-];

 //    for(i=0;i<=tot;i++)for(k1=0;k1<=tot;k1++)if(fa[i][j][k1])printf("  %d->%d\n",k1,i);

 }

 inline void run_f(int j){

     int i,k;register int k1;//printf("j:%d\n",j);

     for(i=;i<=tot;i++)for(k=;k<=tot;k++)if(fa[k][j][i]){

         for(k1=;k1<=tot;k1++)if(fa[k1][j-][i]&&fa[k][j-][k1])

             upd(f[i][j][k],f[i][j-][k1]+f[k1][j-][k]);//,printf("    %d-->%d-->%d\n",i,k1,k);

     }else f[i][j][k]=-inf;

 }

 inline void run_merge(int j){

     int i,k;register int k1;

     if(first){

         first=;

         for(i=;i<=tot;i++)for(k=;k<=tot;k++)g[i][now][k]=f[i][j-][k];

         return;

     }

     for(i=;i<=tot;i++)for(k=;k<=tot;k++)

         for(g[i][now][k]=-inf,k1=;k1<=tot;k1++)if(fa[k][j-][k1])

             upd(g[i][now][k],g[i][pre][k1]+f[k1][j-][k]);

 }

 int main(){

     n=read(),scanf("%I64d",&L);

     for(i=;i<=n;i++)v[i]=read();

     for(i=;i<=n;i++)scanf("%s",s+),trie(strlen(s+),v[i]);

     getfail();

     int a=;

     for(i=;i<=tot;i++)for(k=;k<=tot;k++)f[i][][k]=-inf;

     for(i=;i<=tot;i++)for(j=;j<;j++)fa[next[i][j]][][i]=,f[i][][next[i][j]]=val[next[i][j]];

 //    for(i=0;i<=tot;i++)for(int k1=0;k1<=tot;k1++)if(fa[i][0][k1])printf("  %d->%d\n",k1,i);

     now=,pre=;

     while(L){

         a++;

         if(L&)run_merge(a),swap(now,pre);

         L>>=;

         if(!L)break;

         run_fa(a),run_f(a);

     }

     ll ans=;

     for(i=;i<=tot;i++)upd(ans,g[][pre][i]);

     printf("%I64d\n",ans);

 }

比赛的时候这道题肝了整整1h。。。最后1min才过的样例..竟然就过掉了

巴特西

[Codeforces 696D] Legen...

最新文章

热门文章