GRE Words

Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5466    Accepted Submission(s): 678

Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words.
Now George is working on a word list containing N words.
He has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember.
So he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn't want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word.
Note that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence.

1
5
a 1
ab 2
abb 3
baba 5
abbab 8

Case #1: 14

 题目大意：给你N个字符串。让你求最长带权不下降子序列，其中A<B定义为：A为B的子串。（也就是按顺序取N个字符串使得前面是后面字符串的子串）

Get到新姿势：子串问题还可以利用AC自动机的fail树来解决。首先考虑DP，最暴力的方法我们可以无脑O(n^3)转移。但是很容易想到，我们倒着做DP，这样就可以每处理一个串就把它插入AC自动机，转移的时候跑一下AC自动机，就可以把复杂度降低为O(n^2)，但是还是过不了这道题的。

这个时候我们就需要用到fail树的性质了——

对当前字符串考虑它可以转移的字符串在哪里。发现其实在fail树上，如果当前字符串所在节点为u，那么可以从fail树u的子树内的所有节点转移过来。那么就变成了一个子树信息维护的问题。考虑优化转移：dp到当前串时，首先将当前串插入AC自动机，然后查询当前串所在fail树节点的子树内的所有串的dp值的最大值。最后我们把当前串的dp值扔进线段树：把该串在AC自动机上一路走到的所有节点的dp值都和当前的dp值取max。由于保证字符个数不超过3*10^5，所以我们只需要暴力单点修改即可，总复杂度(n * log(n))

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxc = 3e5 + 5;
const int maxn = 2e4 + 5;
int n, w[maxn], ord[maxn];
char s[maxc];

struct edge {
    int v, next;
}e[maxc];
int head[maxc], cnt;
void adde(const int &u, const int &v) {
    e[++cnt] = (edge) {v, head[u]};
    head[u] = cnt;
}

namespace AC {
    int trie[maxc][26], cnt = 1, fa[maxc], p[maxc];
    void init() {memset(trie[1], 0, sizeof(trie[1])), cnt = 1;}
    void insert(char * s, int x) {
        int id, len = strlen(s), now = 1;
        for(register int i = 0; i < len; ++i) {
            id = s[i] - 'a';
            if(trie[now][id]) now = trie[now][id];
            else {
                p[cnt + 1] = now, now = trie[now][id] = ++cnt;
                memset(trie[now], 0, sizeof(trie[now]));
            }
        }
        ord[x] = now;
    }
    void create() {
        int u, v, p;
        queue<int > q;
        q.push(1);
        while(!q.empty()) {
            u = q.front();q.pop();
            for(register int i = 0; i < 26; ++i) {
                if(!trie[u][i]) continue;
                v = trie[u][i], q.push(v), p = fa[u];
                while(p && !trie[p][i]) p = fa[p];
                if(trie[p][i]) {
                    fa[v] = trie[p][i], adde(fa[v], v);
                } else fa[v] = 1, adde(1, v);
            }
        }
    }
}

int dfn[maxc], dfe[maxc], dcnt, mx;
void dfs(int u) {
    dfn[u] = ++dcnt;
    for(register int i = head[u]; i; i = e[i].next)
        dfs(e[i].v);
    dfe[u] = dcnt;
}

namespace SGT {
    int mx[maxc << 2];
    void push_up(int rt) {
        mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
    }
    void edit(int pos, int tl, int tr, int num, int rt) {
        if(tl == tr) {
            if(mx[rt] < num) mx[rt] = num;
            return ;
        }
        int mid = tl + tr >> 1;
        if(pos <= mid) edit(pos, tl, mid, num, rt << 1);
        else edit(pos, mid + 1, tr, num, rt << 1 | 1);
        push_up(rt);
    }
    int query(int l, int r, int tl, int tr, int rt) {
        if(l == tl && r == tr) return mx[rt];
        int mid = tl + tr >> 1;
        if(r <= mid) return query(l, r, tl, mid, rt << 1);
        else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
        else return max(query(l, mid, tl, mid, rt << 1), query(mid + 1, r, mid + 1, tr, rt << 1 | 1));
    }
}

int dp[maxn], u, t;
int main() {
    scanf("%d", &t);
    for(register int cs = 1; cs <= t; ++cs){
        memset(dp, 0, sizeof(dp)), mx = 0;
        memset(head, 0, sizeof(head));
        scanf("%d", &n), AC::init(), dcnt = cnt = 0;
        memset(SGT::mx, 0, sizeof(SGT::mx));
        for(register int i = 1; i <= n; ++i)
            scanf("%s%d", s, &w[i]), AC::insert(s, i);
        AC::create(), dfs(1);
        for(register int i = n; i >= 1; --i) {
            u = ord[i];
            dp[i] = SGT::query(dfn[u], dfe[u], 1, dcnt, 1) + w[i], mx = max(mx, dp[i]);
            while(u) SGT::edit(dfn[u], 1, dcnt, dp[i], 1), u = AC::p[u];
        }
        printf("Case #%d: %d\n", cs, mx);
    }
    return 0;
}