题目描述：
有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
西月弦 阅读(1338)
评论(2) 编辑 收藏 引用 所属分类:
解题报告