题意：给出一串单词，每个有一个权值。顺序不变的情况下，删掉一些，使得相邻两单词，前一个是后一个的子串。同时要求使得剩余单词权值和最大。求最大是多少。
分析：
AC自动机+线段树+DP。
这是一个比较复杂的题目，我们分步来讲解。
第一部分，动态规划。
用f[i]表示从第1个单词，到第i个单词，所有剩余单词中包含第i个的情况中最大权值和是多少。
f[i]=max(f[v]+weight[i])，要求第v个单词是第i个单词的子串且v<i。
第二部分，利用AC自动机求所有子串。
fail指针就是找后缀，一个串的子串就是某前缀的后缀。因此我们在建立好自动机之后将一个串重新从root节点开始走，
第三部分，fail树的建立。
我们不是真正的通过fail指针找某串的子串，而是通过fail反向指针找所有以该串为后缀的串。
由于每个节点只有一个fail指针，因此我们可以从root开始利用fail指针的逆指针建立一个fail树。
这个树的意义是，其中每个节点的祖先都是它的后缀。每个节点的子孙都是在该节点的串的前面加入了不同的内容产生的。
我们给fail树中的每个节点v附加一个额外的值f[v](就是第一部分中说的)，f[v]的值更新之后会影响到fail树中该串对应节点的子孙的f值。
当我们要计算f[i]时，要分别观察a的所有前缀所在fail树中的值。f[i]=max(f[v]+weight[i])，v是i的所有前缀在fail树中的所有祖先。
现在问题变成了一个，动态改变树中点的权值，并询问某点的祖先中最大值的问题。可以用线段树来解决。
先对fail树进行时间戳标记，这样每个子树对应一个区间，然后每个权值的改变都更新线段书上的一个区间（fail树中的一个子树）即可。
询问时分别询问每个前缀的f[i]取最大即可。
树的时间戳标记模板如下：
void dfs(int u, int parent)
{
dfn[u][] = ++dfn_cnt;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].v;
if (v != parent)
{
dfs(v, u);
}
}
dfn[u][] = dfn_cnt;
}
线段树框架模板如下：
struct SegmentTree
{ struct Node
{
int l, r;
Node *pleft, *pright;
//add the needed variable
}tree[MAX_INTERVAL *]; int node_cnt; void init()
{
node_cnt = ;
} Node* new_node()
{
node_cnt++;
return tree + node_cnt;
} void build_tree(Node *proot, int s, int e)
{
proot->l = s;
proot->r = e;
//init the variables
if (s == e)
{
proot->pleft = proot->pright = NULL;
return;
}
int mid = (s + e) / ;
build_tree(proot->pleft = new_node(), s, mid);
build_tree(proot->pright = new_node(), mid + , e);
} void pull_up(Node *proot)
{
//do something
} void push_down(Node *proot)
{
//do something
} void update(Node *proot, int start, int end, int value)
{
if (start > proot->r || end < proot->l)
return;
start = max(start, proot->l);
end = min(end, proot->r);
if (start == proot->l && end == proot->r)
{
//do something
return;
}
push_down(proot);
update(proot->pleft, start, end, value);
update(proot->pright, start, end, value);
pull_up(proot);
} int query(Node *proot, int start, int end)
{
int ret = proot->value;
if (start > proot->r || end < proot->l)
return ;
start = max(start, proot->l);
end = min(end, proot->r);
if (start == proot->l && end == proot->r)
{
//do something
}
push_down(proot);
ret = max(ret, query(proot->pleft, start, end));
ret = max(ret, query(proot->pright, start, end));
pull_up(proot);
return ret;
}
};
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std; #define D(x) const int MAX_CHILD_NUM = ;
const int MAX_NODE_NUM = * (int)1e5 + ;
const int MAX_LEN = * (int)1e5 + ;
const int MAX_N = * (int)1e4 + ; #define MAX_EDGE_NUM MAX_NODE_NUM * 2 struct Edge
{
int v, next;
Edge()
{}
Edge(int v, int next):v(v), next(next)
{}
} edge[MAX_EDGE_NUM]; int head[MAX_NODE_NUM];
int edge_cnt; void init_edge()
{
memset(head, -, sizeof(head));
edge_cnt = ;
} void add_edge(int u, int v)
{
edge[edge_cnt] = Edge(v, head[u]);
head[u] = edge_cnt++;
} struct Trie
{
int next[MAX_NODE_NUM][MAX_CHILD_NUM];
int fail[MAX_NODE_NUM];
int count[MAX_NODE_NUM];
int node_cnt;
int root;
bool vis[MAX_NODE_NUM]; //set it to false void init()
{
node_cnt = ;
root = newnode();
} int newnode()
{
for (int i = ; i < MAX_CHILD_NUM; i++)
next[node_cnt][i] = -;
count[node_cnt++] = ;
return node_cnt - ;
} int get_id(char a)
{
return a - 'a';
} void insert(char buf[], int index)
{
int now = root;
for (int i = ; buf[i]; i++)
{
int id = get_id(buf[i]);
if (next[now][id] == -)
next[now][id] = newnode();
now = next[now][id];
}
count[now] = index;
} void build()
{
queue<int>Q;
fail[root] = root;
for (int i = ; i < MAX_CHILD_NUM; i++)
if (next[root][i] == -)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while (!Q.empty())
{
int now = Q.front();
Q.pop();
for (int i = ; i < MAX_CHILD_NUM; i++)
if (next[now][i] == -)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
} void debug()
{
for(int i = ;i < node_cnt;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],count[i]);
for(int j = ;j < MAX_CHILD_NUM;j++)
printf("%2d",next[i][j]);
printf("]\n");
}
} void build_fail_tree()
{
init_edge();
for (int i = ; i < node_cnt; i++)
{
add_edge(i, fail[i]);
add_edge(fail[i], i);
}
} }ac; const int MAX_INTERVAL = MAX_LEN; struct SegmentTree
{ struct Node
{
int l, r;
Node *pleft, *pright;
int value;
}tree[MAX_INTERVAL *]; int node_cnt; void init()
{
node_cnt = ;
} Node* new_node()
{
node_cnt++;
return tree + node_cnt;
} void build_tree(Node *proot, int s, int e)
{
proot->l = s;
proot->r = e;
proot->value = ;
if (s == e)
{
proot->pleft = proot->pright = NULL;
return;
}
int mid = (s + e) / ;
build_tree(proot->pleft = new_node(), s, mid);
build_tree(proot->pright = new_node(), mid + , e);
} void pull_up(Node *proot)
{
} void push_down(Node *proot)
{
} void update(Node *proot, int start, int end, int value)
{
if (start > proot->r || end < proot->l)
return;
start = max(start, proot->l);
end = min(end, proot->r);
if (start == proot->l && end == proot->r)
{
proot->value = max(proot->value, value);
return;
}
push_down(proot);
update(proot->pleft, start, end, value);
update(proot->pright, start, end, value);
pull_up(proot);
} int query(Node *proot, int start, int end)
{
int ret = proot->value;
if (start > proot->r || end < proot->l)
return ;
start = max(start, proot->l);
end = min(end, proot->r);
if (start == proot->l && end == proot->r)
{
return ret;
}
push_down(proot);
ret = max(ret, query(proot->pleft, start, end));
ret = max(ret, query(proot->pright, start, end));
pull_up(proot);
return ret;
}
}tree; char st[MAX_LEN];
int pos[MAX_N];
int dfn[MAX_LEN][];
int dfn_cnt;
int n;
int weight[MAX_N]; void dfs(int u, int parent)
{
dfn[u][] = ++dfn_cnt;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].v;
if (v != parent)
{
dfs(v, u);
}
}
dfn[u][] = dfn_cnt;
} int work()
{
int ret = ;
tree.init();
tree.build_tree(tree.tree, , dfn_cnt);
for (int i = ; i < n; i++)
{
int u = ac.root;
int temp = ;
for (int j = pos[i]; j < pos[i + ]; j++)
{
u = ac.next[u][ac.get_id(st[j])];
temp = max(temp, tree.query(tree.tree, dfn[u][], dfn[u][]) + weight[i]);
}
tree.update(tree.tree, dfn[u][], dfn[u][], temp);
ret = max(ret, temp);
}
return ret;
} void input()
{
scanf("%d", &n);
int temp = ;
for (int i = ; i < n; i++)
{
scanf("%s%d", st + temp, &weight[i]);
pos[i] = temp;
ac.insert(st + temp, i);
int len = strlen(st + temp);
temp += len;
}
pos[n] = temp;
} int main()
{
int t;
scanf("%d", &t);
for (int i = ; i <= t; i++)
{
ac.init();
input();
ac.build();
ac.build_fail_tree();
dfn_cnt = ;
dfs(, -);
printf("Case #%d: %d\n", i, work());
}
return ;
}