題意：給定一張包含 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); freopen("p3.out", "w", stdout); #endif for (scanf("%d", &T); T--; ) { int i, ans = 0; prepare(), scanf("%d", &n); FOR(i, 1, n) scanf("%s%d", st, w + i), insert(st, i); build(); dfs(); build(nRT, 1, cnt); ROF(i, n, 1) { int k = ask(begin[i], end[i]) + w[i]; maxim(ans, k); for (trie *p = tback[i]; p != root; p = p->fa) insert(mark[p - root], k); } printf("%d\n", ans); } return 0; } 後綴數組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 #define maxm 2005 typedef int array[maxn]; typedef int arr[maxk]; array sa, rank, sum, xx, yy, z, height, st; void build(int &n, int &m) { int i, j, k; int *x = xx, *y = yy; memset(sum, 0, sizeof(array)); FOR(i, 1, n) ++sum[x[i] = st[i]]; FOR(i, 2, m) sum[i] += sum[i - 1]; ROF(i, n, 1) sa[sum[x[i]]--] = i; for (j = 1; m < n; j <<= 1, m = k) { k = 0; FOR(i, n - j + 1, n) y[++k] = i; FOR(i, 1, n) if (sa[i] > j) y[++k] = sa[i] - j; memset(sum, 0, sizeof(array)); FOR(i, 1, n) ++sum[z[i] = x[y[i]]]; FOR(i, 2, m) sum[i] += sum[i - 1]; ROF(i, n, 1) sa[sum[z[i]]--] = y[i]; swap(x, y), x[sa[1]] = k = 1; FOR(i, 2, n) { int p = sa[i], q = sa[i - 1]; x[p] = y[p] == y[q] && y[p + j] == y[q + j] ? k : ++k; } } memcpy(rank, x, sizeof(array)); FOR(i, 1, n) { j = sa[rank[i] - 1]; z[i] = z[i - 1] ? z[i - 1] - 1 : 0; for (; st[i + z[i]] == st[j + z[i]]; ++z[i]); height[rank[i]] = z[i]; } } int back[200], L, ans; array belong; arr w, len, begin, end; void init(int &n, int &m) { int i, j, k; memset(back, 0, sizeof back); scanf("%d\n", &n), m = n; int *ptr = st; FOR(i, 1, n) { begin[i] = k = j = ptr - st + 1; for (*(++ptr) = getchar(); 'a' <= *ptr && *ptr <= 'z'; *(++ptr) = getchar()) { if (!back[*ptr]) back[*ptr] = ++m; *ptr = back[*ptr]; belong[k] = i, ++k; } *ptr = i, belong[end[i] = ptr - st] = 0; len[i] = ptr - st - j; scanf("%d\n", w + i); } L = ptr - st; } namespace rmq { array mini[19]; void prepare() { int i, j; int *p = mini[0], *q; FOR(i, 1, L) p[i] = height[i]; FOR(i, 1, 18) { q = p, p = mini[i]; FOR(j, 1, L) p[j] = min(q[j], q[j + (1 << (i - 1))]); } } } namespace tree { struct node { node *s, *t, *f; int l, r, v; }; node ns[maxn*2], *nt = ns, *root, *back[maxn]; int L, R, 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 init(int r) {nt = ns; build(root, 1, r);} void insert(int pos, int k) { node *p = back[pos]; p->v = k; for (p = p->f; p; p = p->f) p->v = max(p->s->v, p->t->v); } void query(node *p) { if (L <= p->l && p->r <= R) {ans = p->v; return;} if (L <= p->s->r && p->s->v > ans) query(p->s); if (p->t->l <= R && p->t->v > ans) query(p->t); } int query(int l, int r) {return ans = 0, L = l, R = r, query(root), ans;} } void work(int n) { int i, j, k, l, x, y; ans = 0; rmq::prepare(), tree::init(L); ROF(i, n, 1) { int pos = rank[begin[i]], ll, rr; l = len[i], ll = rr = pos, ++rr; ROF(j, 19, 0) if ((x = rr + (1 << j) - 1) < L) if (rmq::mini[j][rr] >= l) rr = x; ROF(j, 19, 0) if ((x = ll - (1 << j) + 1) > 0) if (rmq::mini[j][x] >= l) ll = x; maxim(ans, k = tree::query(ll, rr) + w[i]); x = begin[i], y = end[i]; for (j = x; j < y; ++j) tree::insert(rank[j], k); } printf("%d\n", ans); } int main() { #ifndef ONLINE_JUDGE freopen("p3.in", "r", stdin); freopen("p3.out", "w", stdout); #endif www.2cto.com int T, n, m; for (scanf("%d", &T); T--; ) { init(n, m); build(L, m); work(n); } return 0; }
