题意: http://acm.hdu.edu.cn/showproblem.php?pid=4117
思路:
主要就是卡你内存, AC 自动机的字典树得要用了再清空.
代码有点长吧...
- #include <cstdio>//sprintf islower isupper
- #include <iostream>//pair
- #include <string.h>//strstr substr strcat
- #include <queue>//priority_queue<int, vector<int>, greater<int>> q;//Less
- using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
- #define mem(a,b) memset(a,b,sizeof(a))
- #define pr printf
- #define sc scanf
- #define ls rt<<1
- #define rs rt<<1|1
- const int N=3e5+10;
- char s[N];
- int pos[20004],val[20004];
- //-------------------------------
- class mymap
- {
- public:
- int tot;
- int head[N];
- int SZ[N];
- int dfn[N],cnt;
- struct
- {
- int to,next;
- }edge[N];
- void Init(int n)
- {
- tot=0;
- cnt=-1;
- for(int i=0;i<=n;++i)
- head[i]=SZ[i]=0;
- }
- void add(int from,int to)
- {
- ++tot;
- edge[tot].to=to;
- edge[tot].next=head[from];
- head[from]=tot;
- }
- int dfs(int u)
- {
- ++cnt;
- dfn[u]=cnt;
- SZ[dfn[u]]=1;
- for(int i=head[u];i;i=edge[i].next)
- {
- // cout<<edge[i].first<<endl;
- SZ[dfn[u]]+=dfs(edge[i].to);
- }
- return SZ[dfn[u]];
- }
- }TREE;
- class seg_tree
- {
- public:
- int max_[N<<2],add[N<<2];
- void up(int rt)
- {
- max_[rt]=max(max_[ls],max_[rs]);
- }
- void dn(int rt)
- {
- if(add[rt])
- {
- add[ls]=max(add[ls],add[rt]);
- add[rs]=max(add[rs],add[rt]);
- max_[ls]=max(max_[ls],add[rt]);
- max_[rs]=max(max_[rs],add[rt]);
- add[rt]=0;
- }
- }
- void Build(int l,int r,int rt)
- {
- max_[rt]=0;
- add[rt]=0;
- if(l==r)
- {
- return;
- }
- int mid=(l+r)>>1;
- Build(l,mid,rt<<1);
- Build(mid+1,r,rt<<1|1);
- }
- int Q_dot(int pos,int l,int r,int rt)
- {
- if(l==r)
- {
- return max_[rt];
- }
- int mid=(l+r)>>1;
- dn(rt);
- if(pos<=mid)
- return Q_dot(pos,l,mid,rt<<1);
- else
- return Q_dot(pos,mid+1,r,rt<<1|1);
- }
- void update_qu(int L,int R,int V,int l,int r,int rt)
- {
- if(L>R)return;
- if(L<=l&&r<=R)
- {
- max_[rt]=max(max_[rt],V);
- add[rt]=max(add[rt],V);
- return;
- }
- int mid=(l+r)>>1;
- dn(rt);
- if(L<=mid)
- update_qu(L,R,V,l,mid,rt<<1);
- if(R>mid)
- update_qu(L,R,V,mid+1,r,rt<<1|1);
- up(rt);
- }
- }SEG;
- class ac_automaton
- {
- public:
- int tot;
- int trie[N][27];
- int fail[N];
- //other
- //--------------
- void Insert(int l,int r)
- {
- int rt=0;
- for(int i=l;i<=r;++i)
- {
- int id=s[i]-'a'+1;
- if(!trie[rt][id])
- {
- mem(trie[++tot],0);
- trie[rt][id]=tot;
- }
- rt=trie[rt][id];
- }
- }
- queue<int>q;
- void Getfail()
- {
- for(int i=1;i<=26;++i)
- {
- int id=trie[0][i];
- if(id)
- {
- fail[id]=0;
- q.push(id);
- }
- }
- while(!q.empty())
- {
- int rt=q.front();q.pop();
- for(int i=1;i<=26;++i)
- {
- int id=trie[rt][i];
- if(id)
- {
- fail[id]=trie[fail[rt]][i];
- q.push(id);
- }
- else
- trie[rt][i]=trie[fail[rt]][i];
- }
- }
- }
- int Find(int l,int r,int id,int n)
- {
- int rt=0;
- int pos=0;
- int temp_max=0;
- for(int i=l;i<=r;++i)
- {
- rt=trie[rt][s[i]-'a'+1];
- pos=TREE.dfn[rt];
- int temp_val=SEG.Q_dot(pos,1,n,1)+val[id];
- temp_max=max(temp_max,temp_val);
- }
- SEG.update_qu(pos,pos+TREE.SZ[pos]-1,temp_max,1,n,1);
- // for(int j=1;j<=n;++j)pr("%d",SEG.Q_dot(j,1,n,1));
- // cout<<endl<<"----------------------------------"<<endl;
- return temp_max;
- }
- }AC;
- void solve()
- {
- AC.tot=0;
- mem(AC.trie[0],0);
- int n,tot;
- sc("%d",&n);
- pos[1]=1;
- for(int i=1;i<=n;++i)
- {
- sc("%s %d",s+pos[i],&val[i]);
- int l=strlen(s+pos[i]);
- AC.Insert(pos[i],pos[i]+l-1);
- pos[i+1]=pos[i]+l;
- }
- tot=AC.tot;
- // pr("%s\n",s+1);
- AC.Getfail();
- TREE.Init(tot);
- SEG.Build(1,tot,1);
- for(int i=1;i<=AC.tot;++i)
- TREE.add(AC.fail[i],i);
- TREE.SZ[0]=TREE.dfs(0);
- int ans=0;
- for(int i=1;i<=n;++i)
- ans=max(ans,AC.Find(pos[i],pos[i+1]-1,i,tot));
- pr("%d\n",ans);
- }
- int main()
- {
- int T,cnt=0;
- sc("%d",&T);
- while(T--)
- {
- pr("Case #%d:",++cnt);
- solve();
- }
- return 0;
- }
- /**************************************************************************************/
来源: http://www.bubuko.com/infodetail-3309081.html