HDu 4117 GRE Words(acオートマチックセグメントツリーdp)
10743 ワード
参照:http://blog.csdn.net/no__stop/article/details/12287843
この問題はacオートマチックfailツリーの性質を利用して、failポインタはツリーとして創立して、親ノードが子供ノードの接尾辞であることを表します
次に、影響する文字列を更新する方法、すなわち、区間を更新し、最大値を維持し、セグメントツリーで最適化します.
影響を及ぼす文字列はfailツリーのサブツリーノードです
この問題はずっとMLEで、午後+夜に調整しました.最後に発見した.
(1)acオートマトンのノードが直接初期化を開始し,動的に初期化すべきである(多くの人がそうすることもやっと理解した)
(2)またvectorで木の辺を表す場合,最初はclearで,メモリも多く消費される.
(3)線分ツリーはCLR(smax,0)CLR(cov,0)を直接初期化し始め,配列が大きいためメモリ消費量が大きい
最後に、acオートマトンノードが動的に初期化され、チェーンテーブルシミュレーションでツリーエッジが表示され、セグメントツリーが動的にbuildされ、ついにMLEがwaになった.
怒ってたたき直して、やっとacしました
PS:最初は接尾辞配列acを使っていましたが、データ水が..
ただしacオートマチック2 s+、接尾辞配列8 s+
acオートマチック:
接尾辞配列:
この問題はacオートマチックfailツリーの性質を利用して、failポインタはツリーとして創立して、親ノードが子供ノードの接尾辞であることを表します
次に、影響する文字列を更新する方法、すなわち、区間を更新し、最大値を維持し、セグメントツリーで最適化します.
影響を及ぼす文字列はfailツリーのサブツリーノードです
この問題はずっとMLEで、午後+夜に調整しました.最後に発見した.
(1)acオートマトンのノードが直接初期化を開始し,動的に初期化すべきである(多くの人がそうすることもやっと理解した)
(2)またvectorで木の辺を表す場合,最初はclearで,メモリも多く消費される.
(3)線分ツリーはCLR(smax,0)CLR(cov,0)を直接初期化し始め,配列が大きいためメモリ消費量が大きい
最後に、acオートマトンノードが動的に初期化され、チェーンテーブルシミュレーションでツリーエッジが表示され、セグメントツリーが動的にbuildされ、ついにMLEがwaになった.
怒ってたたき直して、やっとacしました
PS:最初は接尾辞配列acを使っていましたが、データ水が..
ただしacオートマチック2 s+、接尾辞配列8 s+
acオートマチック:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i >= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(a, v) memset(a, v, sizeof(a))
#define PB push_back
#define MP make_pair
typedef long long LL;
const int INF = 0x3f3f3f3f;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int MAX = 333333;
const int SIG = 26;
struct Edge{
int to, next;
}adj[MAX * 2];
int adj_cnt;
int head[MAX];
void adj_init()
{
adj_cnt = 0;
CLR(head, -1);
}
void add_edge(int x, int y)
{
adj[adj_cnt].to = y;
adj[adj_cnt].next = head[x];
head[x] = adj_cnt++;
}
int tl[MAX], tr[MAX];
int tot;
char ca[MAX], s[MAX];
int id[MAX];
int val[MAX];
int smax[MAX << 2], cov[MAX << 2];
void update_cov(int rt, int x)
{
smax[rt] = max(smax[rt], x);
cov[rt] = max(cov[rt], x);
}
void up(int rt)
{
smax[rt] = max(smax[rt << 1], smax[rt << 1 | 1]);
}
void down(int rt)
{
if (cov[rt])
{
update_cov(rt << 1, cov[rt]); update_cov(rt << 1 | 1, cov[rt]);
cov[rt] = 0;
}
}
void build(int l, int r, int rt)///!!!
{
smax[rt] = cov[rt] = 0;
if (l == r) return ;
int m = (l + r) >> 1;
build(lson); build(rson);
up(rt);
}
void update(int L, int R, int x, int l, int r, int rt)
{
if (L <= l && r <= R)
{
update_cov(rt, x);
return ;
}
down(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, x, lson);
if (R > m) update(L, R, x, rson);
up(rt);
}
int query(int p, int l, int r, int rt)
{
if (l == r) return smax[rt];
down(rt);
int m = (l + r) >> 1;
if (p <= m) return query(p, lson);
else return query(p, rson);
}
struct AC{
int ch[MAX][SIG];
int f[MAX];
int sz;
int newnode()///!!!
{
CLR(ch[sz], 0);
return sz++;
}
void init()
{
sz = 0;
newnode();
}
int idx(char c) { return c-'a'; }
void insert(char *s)
{
int u=0,n=strlen(s);
for(int i=0;i<n;i++)
{
int c=idx(s[i]);
if(!ch[u][c]) ch[u][c] = newnode();
u = ch[u][c];
}
}
void getFail()
{
queue<int> q;
f[0] = 0;
for(int c = 0; c < SIG; c++)
{
int u = ch[0][c];
if(u) { f[u] = 0; q.push(u); }
}
while(!q.empty())
{
int r = q.front(); q.pop();
for(int c = 0; c < SIG; c++)
{
int u = ch[r][c];
if(!u) { ch[r][c] = ch[f[r]][c]; continue; }
q.push(u);
int v = f[r];
while(v && !ch[v][c]) v = f[v];
f[u] = ch[v][c];
}
}
}
void dfs(int u, int fa)
{
tl[u] = ++tot;
for (int r = head[u]; r != -1; r = adj[r].next)
{
int v = adj[r].to;
if (v != fa) dfs(v, u);
}
tr[u] = tot;
}
void makeTree()
{
adj_init();
for (int i = 1; i < sz; i++)///
{
add_edge(i, f[i]); add_edge(f[i], i);
}
tot = 0;
dfs(0, -1);
}
int solve(char *s)
{
int len = strlen(s);
int u = 0;
int now, ans;
ans = now = 0;
build(1, tot, 1);
for (int i = 0; i < len; i++)
{
u = ch[u][s[i] - 'a'];
int valu = query(tl[u], 1, tot, 1);
now = max(now, valu);
if (id[i])
{
if (val[id[i]] > 0) now += val[id[i]];
ans = max(ans, now);
update(tl[u], tr[u], now, 1, tot, 1);
u = now = 0;
}
}
return ans;
}
}ac;
int main()
{
int len;
int n, m;
int T, nc;
nc = 1;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
len = 0;
ac.init();
CLR(id, 0);
for (int i = 1; i <= n;i++)
{
scanf("%s%d", ca, &val[i]);
ac.insert(ca);
int l = strlen(ca);
REP(j, l)
{
s[len++] = ca[j];
}
id[len - 1] = i;
}
ac.getFail();
ac.makeTree();
printf("Case #%d: %d
", nc++, ac.solve(s));
}
}
接尾辞配列:
//#pragma warning (disable: 4786)
//#pragma comment (linker, "/STACK:16777216")
//HEAD
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//LOOP
#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
//STL
#define SZ(V) (int)V.size()
#define PB push_back
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d
", n)
#define WS(s) printf("%s
", s)
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> VI;
const int INF = 1000000000;
const double eps = 1e-10;
const int MAXN=110000 * 4;
int wa[MAXN], wb[MAXN], wv[MAXN], wn[MAXN];
char r[MAXN];
int a[MAXN], sa[MAXN], rank[MAXN], height[MAXN];
int idx[MAXN];
int val[20010];
int len[20010];
int sumlen[20010];
int dp[20010];
int cmp(int *r, int a, int b, int k)
{
return r[a] == r[b] && r[a + k] == r[b + k];
}
void build_sa(int *r, int *sa, int n, int m)
{
int i, j, p;
int *x = wa, *y = wb, *t;
for (i = 0; i < m; i++) wn[i] = 0;
for (i = 0; i < n; i++)wn[x[i] = r[i]]++;///
for (i = 1; i < m; i++) wn[i] += wn[i - 1];
for (i = n - 1; i >= 0; i--) sa[--wn[x[i]]] = i;
for (p = 1, j = 1; p < n; j <<= 1, m = p)
{
for (p = 0, i = n - j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < m; i++) wn[i] = 0;
for (i = 0; i < n; i++) wn[wv[i] = x[y[i]]]++;///
for (i = 1; i < m; i++) wn[i] += wn[i - 1];
for (i = n - 1; i >= 0; i--) sa[--wn[wv[i]]] = y[i];
t = x; x = y; y = t;
x[sa[0]] = 0; p = 1;
for (i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
}
void getHeight(int *r, int *sa, int n)
{
int i, j, k = 0;
for (i = 1; i <= n; i++)
{
rank[sa[i]] = i;
height[i] = 0;
}
for (i = 0; i < n; i++)
{
if (k) k--;
j = sa[rank[i] - 1];
while (r[i + k] == r[j + k]) k++;
height[rank[i]] = k;
}
}
int getid(int x)
{
return idx[sa[x]];
}
int solve(int t, int n)
{
int sum = 0;
FE(i, 1, t)
{
dp[i] = val[i];
sumlen[i] = sum;
sum += len[i] + 1;
}
int nowi;
FED(i, t, 1)
{
nowi = sumlen[i];
int lmin = INF;
for (int j = rank[nowi] + 1; j <= n; j++)
{
lmin = min(lmin, height[j]);
if (lmin < len[i]) break;
if (nowi < sa[j])
dp[i] = max(dp[i], val[i] + dp[getid(j)]);
}
lmin = INF;
for (int j = rank[nowi] - 1; j > 0; j--)
{
lmin = min(lmin, height[j + 1]);
if (lmin < len[i]) break;
if (nowi < sa[j])
dp[i] = max(dp[i], val[i] + dp[getid(j)]);
}
}
int ans = 0;
FE(i, 1, t) ans = max(ans, dp[i]);
return ans;
}
int main()
{
int test;
int t, n, m;
int ncase = 1;
RI(test);
while (test--)
{
n = 0;
m = 256;
CLR(idx, 0);
RI(t);
FE(i, 1, t)
{
RS(r);
RI(val[i]);
int l = len[i] = strlen(r);
REP(j, l)
{
a[n] = (int)r[j];
idx[n++] = i;
}
a[n++] = m++;
}
a[--n] = 0; --m;
build_sa(a, sa, n + 1, m);
getHeight(a, sa, n);
printf("Case #%d: %d
", ncase++, solve(t, n));
}
return 0;
}