算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    有N(N<20,000)个只含有小写字母的字符串,总长不超过300,000,每个字符串Si有权值Vi。现在让你删除一些字符串,满足对于相邻的串,前一个串是后一个串的子串。求最大权值和。

算法分析:

    这题必须对AC自动机有足够的理解。。。。
    离线建立AC自动机(在线建立是不可以的,至少我不会)。保证fail指针的正确。
    然后按顺序“插入”串,按照fail指针撸一遍(撸到底)。在撸的过程中DP。
    最坏的情况是sqrt(300,000)*20,000。
#include<iostream>
#include<cassert>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 300005;
const int M = 20005;
char ch[N+M];
int dp[M],trie[N][26],fail[N],word[N],pos[M],sz,Q[N],flag[N];
inline void chkmax(int &a,const int b){if(a<b)a=b;}
void ins(int s){
    for(int p=0;ch[s];s++){
        int x = ch[s] - 'a';
        if(trie[p][x]==0){
            ++sz;
            memset(trie[sz],0,sizeof(trie[sz]));
            word[sz] = 0;
            trie[p][x] = sz;
        }
        p = trie[p][x];
    }
}
void ac(){
    int head = 0, tail = 0;
    for(int i=0;i<26;i++) if(trie[0][i]){
        fail[trie[0][i]] = 0;
        Q[tail ++] = trie[0][i];
    }
    while(head < tail){
        int u = Q[head++],v;
        for(int i=0;i<26;i++)
            if(v = trie[u][i]){
                fail[v] = trie[fail[u]][i];
                Q[tail++] = v;
            }
            else trie[u][i] = trie[fail[u]][i];
    }
}
void cal(int now){
    int p=0,v=0;
    for(int s=pos[now];s<pos[now+1];s++){
        int x = ch[s] -'a',t = (p = trie[p][x]);
        while(t){ 
            if(word[t]) chkmax(v, dp[flag[word[t]]]);
            t = fail[t];
        }
    }
    dp[now] += v;
    word[p] = p;
    flag[p] = now;
}
int main(){
    int test = 0;
    cin >> test;
    for(int _=1;_<=test;_++){
        int n;
        sz = 0;
        scanf("%d",&n);
        pos[0] = 0;
        memset(trie[0],0,sizeof(trie[0]));
        for(int i=0;i<n;i++){
            scanf("%s%d",ch+pos[i],&dp[i]);
            pos[i+1] = pos[i] + strlen(ch+pos[i]);
            ins(pos[i]);
        }
        ac();
        int ans = 0;
        for(int i=0;i<n;i++){
            if(dp[i]>0)
                cal(i);
            chkmax(ans,dp[i]);
        }
        printf("Case #%d: %d\n",_,ans);
    }
    return 0;
}
posted on 2012-07-23 12:52 西月弦 阅读(1206) 评论(2)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: hdu 4117 AC自动机 + DP
2013-09-29 16:10 | luyuncheng
这题好像是随机生成数据,好像得用线段树优化,不然超时。  回复  更多评论
  
# re: hdu 4117 AC自动机 + DP[未登录]
2013-11-07 13:23 | figo
@luyuncheng
对,我去年做的时候是超时了,当时清晨刷题都刷迷糊了,误以为自己AC了 = =  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理