PerfectPan
;

BZOJ 2905 背单词

September 28, 2018

题目链接https://darkbzoj.tk/problem/2905

题意:给定一张包含 NN 个单词的表,每个单词有个价值 WW。要求从中选出一个子序列使得其中的每个单词是后一个单词的子串,最大化子序列中 WW 的和。

思路:首先对所有单词建立 ACAC 自动机,SSTT 的子串等价于 TT 的某个前缀通过 failfail 链可以走到 SS 的终止节点,即 SS 的终止节点是 TT 某个前缀在 failfail 树上的祖先。我们定义 f[i]f[i] 为到第 ii 个单词为止选了 ii 获得的最大价值,则我们有转移方程:

f[i]=max(f[j])+w[i](j<i)f[i]=max(f[j])+w[i] (j< i)

jjii 的子串,假设我们已经求出了 [1,i1][1,i-1]ff 值,它们对后面位置的影响只可能在它们终止节点的子树里,所以我们拿一个线段树维护 failfaildfsdfs 序的区间最大值,每次求完 f[i]f[i] 以后对它所在的子树区间更新它的 dpdp 值,求 f[i]f[i] 求相当于单点查询字符串 ii 每个前缀的节点 dfsdfs 序上的值了,时间复杂度 O(LlogL)O(L\log L)

#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int SIGMA_SIZE=26;
const int N=3e5+10;
const int M=20000+10;
char s[N];
int T,n,i,j,tot,dfs_clock,st[N],ed[N],w[M],fail[N],son[N][SIGMA_SIZE];
ll tag[N<<2];
vector<int>pos[M],G[N];
queue<int>Q;
void ins(char* s,int j){
    int p=1;
    for (int i=0;s[i];++i){
        int idx=s[i]-'a';
        if (!son[p][idx]) son[p][idx]=++tot;
        p=son[p][idx];
        pos[j].PB(p);
    }
}
void getfail(){
	fail[1]=1;
	for (int i=0;i<SIGMA_SIZE;++i){
		if (!son[1][i]) son[1][i]=1;
		else{
			fail[son[1][i]]=1;
			Q.push(son[1][i]);
		}
	}
    while (!Q.empty()){
        int u=Q.front();Q.pop();
        for (int i=0;i<SIGMA_SIZE;++i){
            if (!son[u][i]) son[u][i]=son[fail[u]][i];
            else{
                fail[son[u][i]]=son[fail[u]][i];
                Q.push(son[u][i]);
            }
        }
    }
}
void dfs(int u){
    st[u]=++dfs_clock;
    for (int i=0;i<(int)G[u].size();++i){
        int v=G[u][i];
        dfs(v);
    }
    ed[u]=dfs_clock;
}
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
inline void up(ll&a,ll b){if(a<b)a=b;}
void build(int root,int l,int r){
    tag[root]=0;
    if (l==r) return;
    int mid=l+((r-l)>>1);
    build(lson);
    build(rson);
}
void query(int root,int l,int r,int pos,ll& dp){
    up(dp,tag[root]);
    if (l==r) return;
    int mid=l+((r-l)>>1);
    if (pos<=mid) query(lson,pos,dp);
    else query(rson,pos,dp);
}
void update(int root,int l,int r,int L,int R,ll val){
    if (L<=l && r<=R){
        up(tag[root],val);
        return;
    }
    int mid=l+((r-l)>>1);
    if (L<=mid) update(lson,L,R,val);
    if (mid<R) update(rson,L,R,val);
}
int main(){
    for (read(T);T--;){
        read(n);
        for (tot=i=1;i<=n;++i){
            scanf("%s%d",s,&w[i]);
            if (w[i]<=0) continue;
            pos[i].clear();
            ins(s,i);
        }
        getfail();
        for (i=2;i<=tot;++i) G[fail[i]].PB(i);
        dfs_clock=0,dfs(1);
        build(1,1,tot);
        ll ans=0;
        for (i=1;i<=n;++i){
            if (w[i]<=0) continue;
            ll dp=0;
            int final=0;
            for (j=0;j<(int)pos[i].size();++j){
                int v=pos[i][j];
                query(1,1,tot,st[v],dp);
                if (j+1==(int)pos[i].size()) final=pos[i][j];
            }
            up(ans,dp+=w[i]);
            update(1,1,tot,st[final],ed[final],dp);
        }
        printf("%lld\n",ans);
        for (i=1;i<=tot;++i){
            G[i].clear();
            for (j=0;j<SIGMA_SIZE;++j) son[i][j]=0;
        }
    }
    return 0;
}

Yiming Pan

Written by Yiming Pan who lives and works in Hangzhou China. Welcome follow me on Github

Cannot load comments. Please check you network.