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;
}