Wannafly Camp 2020 Day 2K 破忒头的匿名信

给定字典和文章，每个单词有价值，求写文章的最小价值

标准的 AC 自动机 dp，设 \(f[i]\) 表示写 \(s[1..i]\) 的最小价值，建立AC自动机后根据 trans 边暴力转移即可

建了个中间图结果被卡内存了，被迫删掉

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5+5;

vector <pair<signed,signed> > g[N];

int slen[N],w[N],ttt;

int min(signed x,int y) {return min(1ll*x,y);}

int f[N];

void msgOccur(int len,int pos,int wei) {

    ++pos; ++ttt;

    int p = pos-len;

    //f[i]=min(f[i],f[g[i][j].first]+g[i][j].second);

    //g[pos].push_back(make_pair(p,wei));

    f[pos]=min(f[pos],f[p]+wei);

}

struct ACA{

	signed c[N][26],val[N],fi[N],cnt,ans[N];

	void init(){

		memset(c,0,sizeof c); memset(val,0x3f,sizeof val);

		memset(fi,0,sizeof fi); memset(ans,0,sizeof ans); cnt=0;}

	void ins(char *str,int id){

		int len=strlen(str), p=0;

		for(int i=0;i<len;i++){

			int v=str[i]-'a';

			if(!c[p][v]) c[p][v]=++cnt;

			p=c[p][v];}

		val[p]=min(val[p],w[id]);

		slen[p]=len;}

	void build(){

	    queue <signed> q;

		for(int i=0;i<26;i++) if(c[0][i]) fi[c[0][i]]=0, q.push(c[0][i]);

		while(!q.empty()){

			int u=q.front(); q.pop();

			for(int i=0;i<26;i++)

				if(c[u][i]) fi[c[u][i]]=c[fi[u]][i], q.push(c[u][i]);

				else c[u][i]=c[fi[u]][i];}}

	int query(char *s){

		int len=strlen(s); int p=0;

		for(int i=0;i<len;i++){

			p=c[p][s[i]-'a'];

			for(int t=p;t&&~val[t];t=fi[t])

				msgOccur(slen[t],i,val[t]);}}

} AC;

int n; char p[N]; string mp[N];

signed main(){

	scanf("%lld",&n);

    memset(p,0,sizeof p); AC.init();

    for(int i=1;i<=n;i++) {

        scanf("%s%lld",p,&w[i]);

        AC.ins(p,i);

        mp[i]=p;

        //slen[i]=strlen(p);

    }

    AC.build();

    scanf("%s",p);

    memset(f,0x3f,sizeof f);

    f[0]=0;

    int ans=AC.query(p);

    int len=strlen(p);

    cout<<(f[len]>=len*1000000000?-1:f[len])<<endl;

}

巴特西

Wannafly Camp 2020 Day 2K 破忒头的匿名信 - AC自动机,dp

最新文章

热门文章