@Jerusalem
2015-11-13T16:34:37.000000Z
字数 3427
阅读 1504
傻逼DP,求出深搜序,线段树优化即可。
实在不明白为什么爆内存……先放着,有空再改。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxnode=300005,sigma=26,maxn=20005;
queue<int> Q;
vector<int> G[maxnode];
int num[maxnode];
string S[maxn];
int w[maxn];
int f[maxn];
struct Node{
int ls,rs;
int w;
int Lazy;
Node(){
ls=rs=0;
w=0;
Lazy=0;
}
void Clear(){
ls=rs=0;
w=0;
Lazy=0;
}
};
struct Segement_Tree{
Node tree[maxnode*4];
int root,num;
Segement_Tree(){
root=num=0;
}
void Clear(){
root=num=0;
}
void MakeTree(int& root,int l,int r){
root=++num;
tree[root].Clear();
if(l==r)
return;
int mid=(l+r)/2;
MakeTree(tree[root].ls,l,mid);
MakeTree(tree[root].rs,mid+1,r);
}
void PushDown(int root){
tree[tree[root].ls].Lazy=max(tree[tree[root].ls].Lazy,tree[root].Lazy);
tree[tree[root].rs].Lazy=max(tree[tree[root].rs].Lazy,tree[root].Lazy);
tree[root].Lazy=0;
}
void Maintain(int root){
tree[root].w=max(tree[root].Lazy,max(tree[tree[root].ls].w,tree[tree[root].rs].w));
}
void Update(int root,int l,int r,int y1,int y2,int Set){
if(y1<=l&&r<=y2){
tree[root].Lazy=max(tree[root].Lazy,Set);
}
else{
PushDown(root);
int mid=(l+r)/2;
if(y1<=mid)
Update(tree[root].ls,l,mid,y1,y2,Set);
else
Maintain(tree[root].ls);
if(mid<y2)
Update(tree[root].rs,mid+1,r,y1,y2,Set);
else
Maintain(tree[root].rs);
}
Maintain(root);
}
int Query(int root,int l,int r,int y1,int y2){
if(y1<=l&&r<=y2)
return tree[root].w;
int mid=(l+r)/2;
PushDown(root);
Maintain(tree[root].ls);
Maintain(tree[root].rs);
int ans=0;
if(y1<=mid)
ans=max(ans,Query(tree[root].ls,l,mid,y1,y2));
if(mid<y2)
ans=max(ans,Query(tree[root].rs,mid+1,r,y1,y2));
return ans;
}
};
struct Trie{
int tot;
int num;
int ch[maxnode][sigma];
int f[maxnode];
vector<int> G[maxnode];
int l[maxnode];
int r[maxnode];
bool val[maxnode];
Trie(){
tot=1;
num=0;
memset(ch,0,sizeof(ch));
memset(f,0,sizeof(f));
memset(val,false,sizeof(val));
}
void Clear(){
tot=1;
num=0;
memset(ch[0],0,sizeof(ch[0]));
memset(val,false,sizeof(val));
for(int i=0;i<maxnode;i++)
G[i].clear();
}
int newnode(){
memset(ch[tot],0,sizeof(ch[tot]));
return tot++;
}
int idx(char a){
return a-'a';
}
void Insert(string s){
int len=s.length();
int u=0;
for(int i=0;i<len;i++){
if(!ch[u][idx(s[i])])
ch[u][idx(s[i])]=newnode();
u=ch[u][idx(s[i])];
}
val[u]=true;
}
void GetLine(int u){
l[u]=num;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
num++;
GetLine(v);
}
r[u]=++num;
}
void Build(){
while(!Q.empty())
Q.pop();
for(int i=0;i<sigma;i++)
if(ch[0][i]){
f[ch[0][i]]=0;
Q.push(ch[0][i]);
G[0].push_back(ch[0][i]);
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=0;i<sigma;i++){
if(!ch[u][i])
continue;
int v=ch[u][i],r=f[u];
while(r&&!ch[r][i])
r=f[r];
Q.push(v);
f[v]=ch[r][i];
G[f[v]].push_back(v);
}
}
GetLine(0);
}
};
Trie Aho_Corasick;
Segement_Tree DfsOrder;
int n,T;
void Solve()
{
for(int k=1;k<=T;k++){
cin>>n;
Aho_Corasick.Clear();
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++){
cin>>S[i]>>w[i];
Aho_Corasick.Insert(S[i]);
}
int ans=0;
DfsOrder.Clear();
Aho_Corasick.Build();
int l=0,r=Aho_Corasick.num;
DfsOrder.MakeTree(DfsOrder.root,l,r);
for(int i=1;i<=n;i++){
int len=S[i].length();
int u=0;
int tmp=0;
for(int j=0;j<len;j++){
u=Aho_Corasick.ch[u][S[i][j]-'a'];
tmp=max(tmp,DfsOrder.Query(DfsOrder.root,l,r,Aho_Corasick.l[u],Aho_Corasick.l[u])+w[i]);
}
DfsOrder.Update(DfsOrder.root,l,r,Aho_Corasick.l[u],Aho_Corasick.r[u],tmp);
ans=max(ans,tmp);
}
printf("Case #%d: %d\n",k,ans);
}
}
void ReadData()
{
freopen("4117.in","r",stdin);
freopen("4117.out","w",stdout);
ios::sync_with_stdio(false);
cin>>T;
}
void Close()
{
fclose(stdin);
fclose(stdout);
}
int main()
{
ReadData();
Solve();
Close();
return 0;
}