题目
题解
因为是几个数相乘还开根，所以可以对每个值取$\ln$，这样把乘法化成了加法，开根号化成除法，设神力值（取$\lg$）的和为$T$，共有$n$个咒语，最终神力值为$t$，有
$T=t\times n$
一脸分数规划的样子，可以二分$t$，对每个值都$-t$
这样可以建出$AC$自动机在上面$dp$了，设$f_{i,j}$表示填到第$i$位转移到自动机第$j$个节点的最大值，分是否可填两种情况讨论即可，复杂度$O(10n\sum s_i\log \lg V)$？
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# include<cmath>
# include<algorithm>
# define X first
# define Y second
# define mp make_pair
# define Pi pair<int,char>
# define SON son[j][T[i]-'0']
using namespace std;
const int MAX=2e3+5;
const double fs=1e-6;
int n,m,tot;
double A;
double f[MAX][MAX];
char a[MAX],T[MAX],ans[MAX];
Pi tr[MAX][MAX];
struct AC{
int fail[MAX],cnt[MAX];
double val[MAX];
int son[MAX][10];
double ins(int _n,int V)
{
int x=0;
for(int i=1;i<=_n;++i)
{
if(!son[x][a[i]-'0']) son[x][a[i]-'0']=++tot;
x=son[x][a[i]-'0'];
}
return cnt[x]=1,val[x]=log(V);
}
void GET_FAIL()
{
queue<int> qu;
for(int i=0;i<10;++i)
if(son[0][i]) qu.push(son[0][i]);
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
for(int i=0;i<10;++i)
if(son[tt][i]) fail[son[tt][i]]=son[fail[tt]][i],qu.push(son[tt][i]);
else son[tt][i]=son[fail[tt]][i];
val[tt]+=val[fail[tt]],cnt[tt]+=cnt[fail[tt]];
}
}
void Solve(int n,int pos)
{
if(!n) return;
Solve(n-1,tr[n][pos].X),ans[n]=tr[n][pos].Y;
}
bool look(double mid)
{
for(int i=1;i<=tot;++i)
f[0][i]=-1e18;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=tot;++j)
f[i][j]=-1e18;
if(isdigit(T[i]))
{
for(int j=0;j<=tot;++j)
if(f[i-1][j]+val[SON]-mid*cnt[SON]>f[i][SON]) f[i][SON]=f[i-1][j]+val[SON]-mid*cnt[SON],tr[i][SON]=mp(j,T[i]);
}
else for(int j=0;j<=tot;++j)
for(int k=0;k<10;++k)
if(f[i-1][j]+val[son[j][k]]-mid*cnt[son[j][k]]>f[i][son[j][k]])
f[i][son[j][k]]=f[i-1][j]+val[son[j][k]]-mid*cnt[son[j][k]],tr[i][son[j][k]]=mp(j,k+'0');
}
double Mx=-1e18,pos=-1;
for(int i=0;i<=tot;++i)
if(Mx<f[n][i]) Mx=f[n][i],pos=i;
if(Mx<fs) return 0;
return Solve(n,pos),1;
}
}_A;
int main()
{
scanf("%d%d%s",&n,&m,T+1);
for(int i=1,v;i<=m;++i)
scanf("%s%d",a+1,&v),A=max(A,_A.ins(strlen(a+1),v));
_A.GET_FAIL();
double l=0,r=A;
while(l<=r)
{
double mid=(l+r)/2;
if(_A.look(mid)) l=mid+fs;
else r=mid-fs;
}
return printf("%s",ans+1),0;
}
