Loj 3089 奥术神杖

$01$ 分数规划 + AC 自动机.

先把权值取个对数,就变成了最大化算术平均数.

考虑 $01​$ 分数规划,二分答案 $k​$ ,那么每个串的权值变为了 $V_i-k​$ ,需要检验是否存在权值和 $>0​$ 的方案.

注意 $=0​$ 不一定是合法的,因为实际上可能一个串也没有选.

在 AC 自动机上 dp 一下,设 $f(i,j)$ 表示匹配了前 $i$ 个字符,当前在节点 $j$ 时的最大权值, dp 的时候顺便记录方案.

时间复杂度 $O(T\cdot ns|\sum|)$ ,其中 $T$ 表示二分的次数, $|\sum|$ 表示字符集大小.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int MAXN=1515,S=10;
char s[MAXN],buf[MAXN],ans[MAXN];
bool flag=false;
int n,m,idx=0,cnt[MAXN],fail[MAXN],ch[MAXN][S];
double f[MAXN][MAXN],val[MAXN],inf;
void ins(int v)
{
int u=0,len=strlen(buf+1);
for(int i=1;i<=len;++i)
{
int c=buf[i]-'0';
if(!ch[u][c])
ch[u][c]=++idx;
u=ch[u][c];
}
val[u]+=log(v);
cnt[u]++;
}
queue<int> q;
void getfail()
{
for(int i=0;i<S;++i)
if(ch[0][i])
q.push(ch[0][i]);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0;i<S;++i)
if(ch[u][i])
{
q.push(ch[u][i]);
fail[ch[u][i]]=ch[fail[u]][i];
val[ch[u][i]]+=val[fail[ch[u][i]]];
cnt[ch[u][i]]+=cnt[fail[ch[u][i]]];
}
else
ch[u][i]=ch[fail[u]][i];
}
}
int pre[MAXN][MAXN],c[MAXN][MAXN];
bool check(double mid)
{
memset(f,-0x3f,sizeof f);
inf=-f[0][0],f[0][0]=0;
for(int i=0;i<n;++i)
{
int l=(s[i+1]=='.')?0:s[i+1]-'0';
int r=(s[i+1]=='.')?9:s[i+1]-'0';
for(int j=0;j<=idx;++j) if(f[i][j]>-inf)
for(int k=l;k<=r;++k)
{
int p=ch[j][k];
double tmp=f[i][j]+val[p]-mid*cnt[p];
if(tmp>f[i+1][p])
{
f[i+1][p]=tmp;
pre[i+1][p]=j;
c[i+1][p]=k;
}
}
}
double mx=-inf;
int pos;
for(int i=0;i<=idx;++i)
if(f[n][i]>mx)
mx=f[n][i],pos=i;
if(mx<=0)
return false;
for(int i=n;i>=1;--i)
{
ans[i]=c[i][pos]+'0';
pos=pre[i][pos];
}
return true;
}
int main()
{
n=read(),m=read();
scanf("%s",s+1);
double l=0,r=0,mid;
for(int i=1;i<=m;++i)
{
scanf("%s",buf+1);
int v=read();
r=max(r,log(v));
ins(v);
}
getfail();
for(int i=1;i<=30;++i)
{
mid=(l+r)/2.0;
if(check(mid))
flag=true,l=mid;
else
r=mid;
}
if(!flag)
{
for(int i=1;i<=n;++i)
putchar(s[i]=='.'?'0':s[i]);
puts("");
}
else
{
for(int i=1;i<=n;++i)
putchar(ans[i]);
puts("");
}
return 0;
}