HDU2296

• 传送门：HDU2296

傻逼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;
}