The 2011 ACM-ICPC ACRC]G.GRE Words
题意：给定一张包含 N 个单词的表,每个单词有个价值 W。要求从中选出一个子序列使得其中的每个单词是后一个单词的子串,最大化子序列中 W 的和。显然有f[i] = max(f[j] + w[i]), j < i 且串j包含于串i。
将方程化为f[i] = max(f[j] + w[i]), j > i 且串i包含于串j。接着可以考虑用线段树优化去max。
可以用AC自动机或后缀数组做，不过后缀数组由于构建复杂度和二分区间显然要慢得多。
AC自动机code:
[cpp]
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cctype>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#ifdef WIN32
#define fmt64 "%I64d"
#else
#define fmt64 "%lld"
#endif
#define PI M_PI
#define oo 0x13131313
#define PB push_back
#define PO pop_back
#define iter iterator
#define MP make_pair
#define fst first
#define snd second
#define cstr(a) (a).c_str()
#define FOR(i, j, k) for (i = (j); i <= (k); ++i)
#define ROF(i, j, k) for (i = (j); i >= (k); --i)
#define FER(i, j, k) for (i = j[k]; i; i = i->n)
#define FRE(i, a) for (i = (a).begin(); i != (a).end(); ++i)
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
typedef long double real;
template<class T> inline bool minim(T &a, const T &b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool maxim(T &a, const T &b) {return b > a ? a = b, 1 : 0;}
template<class T> inline T sqr(const T &a) {return a * a;}
#define maxn 300005
#define maxk 20005
struct edge {int t; edge *n;}
es[maxn + maxk], *adj, *lst[maxn];
void link(int i, int j)
{
*(++adj) = (edge){j, lst[i]}, lst[i] = adj;
}
struct trie
{
edge *lst;
trie *c[26], *f, *fa;
}
root[maxn], *tt, *que[maxn], *tback[maxk];
void insert(char *st, int k)
{
trie *p = root;
for (; *st; p = p->c[*(st++) - 'a'])
if (!p->c[*st - 'a']) (p->c[*st - 'a'] = ++tt)->fa = p;
*(++adj) = (edge){k, p->lst}, p->lst = adj;
tback[k] = p;
}
void build()
{
int i, ll, rr;
(que[ll = rr = 1] = root)->f = root;
for (; ll <= rr; ++ll)
FOR(i, 0, 25) if (que[ll]->c[i]) {
trie *p = que[ll]->c[i], *q;
for (q = que[ll]->f; q != root && !q->c[i]; q = q->f);
p->f = q->c[i] && q->c[i] != p ? q->c[i] : root;
link(p->f - root, p - root);
que[++rr] = p;
}
}
int T, n, cnt, begin[maxk], end[maxk], mark[maxn];
void dfs()
{
int u, v; trie *p; edge *e;
for (mark[u = 0] = cnt = 0; ; )
if (!lst[u]) {
p = root + u;
for (e = p->lst; e; e = e->n) end[e->t] = cnt;
if (p->f == p) return; else u = p->f - root;
} else {
v = lst[u]->t, lst[u] = lst[u]->n;
u = v, p = root + u, mark[u] = ++cnt;
for (e = p->lst; e; e = e->n) begin[e->t] = cnt;
}
}
struct node
{
node *s, *t, *f;
int l, r, v;
}
ns[maxn*2], *nt, *nRT, *back[maxn];
int nL, nR, ans;
void build(node *&p, int l, int r)
{
p = ++nt, p->l = l, p->r = r, p->v = 0;
if (l == r) {back[l] = p; return;}
build(p->s, l, (l + r) >> 1);
build(p->t, ((l + r) >> 1) + 1, r);
p->s->f = p->t->f = p;
}
void insert(int pos, int k)
{
node *p = back[pos];
if (maxim(p->v, k))
for (p = p->f; p; p = p->f) {
k = max(p->s->v, p->t->v);
if (p->v == k) break; p->v = k;
}
}
void query(node *p)
{
if (nL <= p->l && p->r <= nR) {ans = p->v; return;}
if (nL <= p->s->r && p->s->v > ans) query(p->s);
if (p->t->l <= nR && p->t->v > ans) query(p->t);
}
int ask(int l, int r) {return nL = l, nR = r, ans = 0, query(nRT), ans;}
void prepare()
{
tt = root, memset(root, 0, sizeof root);
adj = es, memset(lst, 0, sizeof lst);
nt = ns;
}
char st[maxn]; int w[maxk];
int main()
{
#ifndef ONLINE_JUDGE
freopen("p3.in", "r", stdin);
freo
补充：软件开发 , C++ ,上一个：C++ Hadoop实战备忘
下一个：c++ _STL基本容器总结介绍
