P5319 [BJOI2019] 奥术神杖

已经调的与这篇题解的代码几乎一模一样了，但还是25pts

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1509;
const double eps=1e-6;
const double INF=1e6;
char t[N],s[N];
int n,m,V,tr[N][13],cnt,g[N][13][2],maxn,sum[N];
double v[N];
int que[N],head,tail,fail[N];
double dp[N][N],l,r,mid;
char ans[N];
inline void build()
{
	int id=0;
	char e;
	for(int i=0;s[i];i++)
	{
		e=s[i];
		if(tr[id][e-'0'])id=tr[id][e-'0'];
		else tr[id][e-'0']=++cnt,id=cnt;
	}
	sum[id]++;
	v[id]+=(double)log((double)V);
}
inline void Fail()
{
	int id;
	head=1;tail=0;
	for(int i=0;i<10;i++)
	 if(tr[0][i])
	  que[++tail]=tr[0][i];
	while(head<=tail)
	{
		id=que[head++];
		sum[id]+=sum[fail[id]];
		v[id]+=v[fail[id]];
		for(int i=0;i<10;i++)
		{
			if(tr[id][i])fail[tr[id][i]]=tr[fail[id]][i],que[++tail]=tr[id][i];
			else tr[id][i]=tr[fail[id]][i];
		}
	}
}
inline bool check()
{
	for(int i=0;i<=cnt;i++)
	 v[i]-=mid*(double)sum[i];
	for(int i=0;i<=n;i++)
	 for(int j=0;j<=cnt;j++)
	  dp[i][j]=-1e100;
	dp[0][0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=cnt;j++)
		{
			if(dp[i][j]<=-1e99)continue;
			if(t[i]=='.')
			{
				for(int k=0;k<10;k++)
				{
					int c=tr[j][k];
					if(dp[i+1][c]<dp[i][j]+v[c])
					{
						dp[i+1][c]=dp[i][j]+v[c];
						g[i+1][c][0]=j,g[i+1][c][1]=k;
					}
				}
			}else{
				int c=tr[j][t[i]-'0'];
				if(dp[i+1][c]<dp[i][j]+v[c])
				{
					dp[i+1][c]=dp[i][j]+v[c];
					g[i+1][c][0]=j,g[i+1][c][1]=t[i]-'0';
				}
			}
		}
	}
	for(int i=0;i<=cnt;i++)
	 v[i]+=mid*(double)sum[i];
	maxn=0;
	for(int i=1;i<=cnt;i++)
	 if(dp[n][i]>dp[n][maxn])
	  maxn=i;
	for(int i=n,kkk=maxn;i;i--)
	 ans[i]=g[i][kkk][1]+'0',kkk=g[i][kkk][0];
	return dp[n][maxn]>0;
}
int main()
{
	scanf("%d%d%s",&n,&m,t);
	for(int i=1;i<=m;i++)
	{
		memset(s,0,sizeof(s));
		scanf("%s%d",s,&V);
		build();
	}
	Fail();
	l=0,r=log(1061109567.0);
	while(r-l>eps)
	{
		mid=(l+r)/2.0;
		if(check())l=mid;
		else r=mid;
	}
	mid=l;
	check();
	printf("%s",ans+1);
}