Loj 3089 奥术神杖

Posted on | Views:

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