[BJOI2019]奥术神杖

https://www.luogu.org/problemnew/show/P5319

题解

首先观察我们要求的答案的形式:

\[\biggl(\prod V_i \biggr)^x\ \ \ x=\frac{1}{c}
\]

这个东西貌似还不能最优化，根据套路论，把这个东西整体取个\(ln\)，于是就变成了：

\[ln\biggl(\biggl(\prod V_i \biggr)^x\biggr)=\frac{1}{x}\sum ln(V_i)
\]

然后这个东西就可以分数规划了，验证的话跑个dp就好了。

有一点就是必须匹配至少一个串，题解好像在状态里加了一维0/1表示有没有匹配到一个串，我是偷懒直接加了个\(eps\)。

代码

#include<bits/stdc++.h>

#define N 1509

using namespace std;

typedef long long ll;

const double eps=1e-5;

queue<int>q;

double dp[N][N],cnt[N],mx[N],w;

int tot,ch[N][10],f[N],n,m,tag1[N][N],tag2[N][N];

char s[N],s1[N];

inline ll rd(){

	ll x=0;char c=getchar();bool f=0;

    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	return f?-x:x;

}

inline void ins(int len){

	int now=0;

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

		if(!ch[now][s1[i]-'0'])ch[now][s1[i]-'0']=++tot;

		now=ch[now][s1[i]-'0'];

	}

	mx[now]+=w;cnt[now]++;

}

inline void build(){

	for(int i=0;i<10;++i)if(ch[0][i])q.push(ch[0][i]);

	while(!q.empty()){

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

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

			if(ch[u][i])f[ch[u][i]]=ch[f[u]][i],mx[ch[u][i]]+=mx[ch[f[u]][i]],

			  cnt[ch[u][i]]+=cnt[ch[f[u]][i]],q.push(ch[u][i]);

			else ch[u][i]=ch[f[u]][i];

		}

	}

}

inline bool check(double mid){

	memset(dp,-0x3f,sizeof(dp));

	dp[0][0]=0;

//	printf("%.2lf   ",mid);

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

//		printf(" ");

		for(int j=0;j<=tot;++j){

			if(s[i]=='.')

			for(int k=0;k<10;++k){

				int x=ch[j][k];

				double xx=dp[i-1][j]+mx[x]-mid*cnt[x];

	//			printf("%.2lf ",xx);

				if(xx>dp[i][x]){

					dp[i][x]=xx;

					tag1[i][x]=k;tag2[i][x]=j;

				}

			}

			else{

				int x=ch[j][s[i]-'0'];

				double xx=dp[i-1][j]+mx[x]-mid*cnt[x];

				if(xx>dp[i][x]){

					dp[i][x]=xx;

					tag2[i][x]=j;

				}

			}

		}

	}

//	puts("");

	for(int j=0;j<=tot;++j)if(dp[n][j]>eps)return 1;

	return 0;

}

void dfs(int len,int now){

	if(!len)return;

	if(s[len]=='.')s[len]=tag1[len][now]+'0';

	dfs(len-1,tag2[len][now]);

//	cout<<now<<" ";printf("%.2lf  ",dp[len][now]);

}

int main(){

	n=rd();m=rd();

	double l=0,r=0;

	scanf("%s",s+1);

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

		scanf("%s",s1+1);w=log((double)rd());

		r=max(r,w);

		ins(strlen(s1+1));

	}

	r+=1000;

	build();

	while(l+eps<r){

		double mid=(l+r)/2;

		if(check(mid))l=mid;

		else r=mid;

	}

//	printf("%.2lf\n",l);

	check(l);

	for(int j=0;j<=tot;++j)if(dp[n][j]>eps){

		dfs(n,j);break;

	}

	printf("%s",s+1);

	return 0;

}