题意：给你若干个串和一个填了一部分的串。补完这个串使得 (每个串的匹配次数 * 权值) ^ (1 / 所有串匹配次数) 最大。
解：把这个东西随便取一个对数，就变成了分数规划。
二分。然后在AC自动机上DP判定。
1 #include <bits/stdc++.h>
2
3 const int N = 1510;
4 const double INF = 1e10, eps = 1e-16;
5
6 int tr[N][26], tot(1), cnt[N], g[N][N], gt[N][N], tans, fail[N], n;
7 double ed[N], f[N][N];
8 char str[N], ss[N];
9
10 inline void getfail() {
11
12 std::queue<int> Q;
13 Q.push(1);
14 fail[1] = 1;
15 while(Q.size()) {
16 int x = Q.front();
17 if(x != 1) {
18 ed[x] += ed[fail[x]];
19 cnt[x] += cnt[fail[x]];
20 }
21 Q.pop();
22 for(int f = 0; f < 10; f++) {
23 if(tr[x][f]) {
24 int y = tr[x][f];
25 if(x == 1) fail[y] = 1;
26 else fail[y] = tr[fail[x]][f];
27 Q.push(y);
28 }
29 else {
30 if(x == 1) tr[x][f] = 1;
31 else tr[x][f] = tr[fail[x]][f];
32 }
33 }
34 }
35 return;
36 }
37
38 inline void insert(double v) {
39 int len = strlen(ss), p = 1;
40 for(int i = 0; i < len; i++) {
41 int f = ss[i] - '0';
42 if(!tr[p][f]) {
43 tr[p][f] = ++tot;
44 }
45 p = tr[p][f];
46 }
47 ed[p] += v;
48 cnt[p]++;
49 return;
50 }
51
52 inline double check(double D) {
53
54 /// f[i][j] means len i in node j , max value
55
56 for(int i = 0; i <= n; i++) {
57 for(int j = 1; j <= tot; j++) {
58 f[i][j] = -INF;
59 }
60 }
61
62 double ans = -INF;
63 f[0][1] = 0;
64 for(int i = 0; i < n; i++) {
65 for(int j = 1; j <= tot; j++) {
66 //if(sgn(f[i][j] + INF) == 0) continue;
67 if(f[i][j] == -INF) continue;
68 //printf("%lf ", f[i][j]);
69 if(str[i + 1] != '.') {
70 int ff = str[i + 1] - '0';
71 int y = tr[j][ff];
72 if(f[i + 1][y] < f[i][j] + ed[y] - D * cnt[y]) {
73 f[i + 1][y] = f[i][j] + ed[y] - D * cnt[y];
74 g[i + 1][y] = j;
75 gt[i + 1][y] = ff;
76 }
77 }
78 else {
79 for(int ff = 0; ff < 10; ff++) {
80 int y = tr[j][ff];
81 //f[i + 1][y] = std::max(f[i + 1][y], f[i][j] + ed[y] - D * cnt[y]);
82 if(f[i + 1][y] < f[i][j] + ed[y] - D * cnt[y]) {
83 //printf("ff = %d y = %d \n", ff, y);
84 f[i + 1][y] = f[i][j] + ed[y] - D * cnt[y];
85 g[i + 1][y] = j;
86 gt[i + 1][y] = ff;
87 }
88 }
89 }
90 }
91 //puts("");
92 }
93
94 for(int j = 1; j <= tot; j++) {
95 if(ans < f[n][j] + eps) {
96 ans = f[n][j];
97 tans = j;
98 }
99 }
100
101 return ans;
102 }
103
104 int main() {
105
106 //freopen("my.out", "w", stdout);
107
108 int m;
109 double l = 0, r = 0;
110 scanf("%d%d", &n, &m);
111 scanf("%s", str + 1);
112 double x;
113 for(int i = 1; i <= m; i++) {
114 scanf("%s%lf", ss, &x);
115 //printf("i = %d \n", i);
116 x = log(x);
117 //printf(" h 21 1 1 \n");
118 insert(x);
119 //printf(" fdsgfdsfsdfsh 21 1 1 \n");
120 r += x;
121 int len = strlen(ss);
122 memset(ss, 0, len * sizeof(char));
123 }
124 //printf("gfsiofdsfsdgfs\n");
125
126 getfail();
127
128 for(int T = 1; T <= 30; T++) {
129 double mid = (l + r) / 2;
130 //printf("mid %.10f \n", mid);
131 double t = check(mid);
132 //printf("l = %lf r = %lf mid = %lf \n", l, r, mid);
133
134 if(t > 0) {
135 l = mid;
136 }
137 else {
138 r = mid;
139 }
140 }
141
142 //printf("r = %.10f \n", r);
143 /// output ways
144 /*
145 6 5
146 2....2
147 252 62
148 5225 18
149 25 7
150 552 12
151 2122 18
152
153 */
154
155 check(l);
156 for(int i = n; i >= 1; i--) {
157 //printf("ans : %d \n", gt[i][tans]);
158 //printf("node : j = %d \n", tans);
159 str[i] = gt[i][tans];
160 tans = g[i][tans];
161
162 }
163
164 for(int i = 1; i <= n; i++) {
165 putchar(str[i] + '0');
166 }
167 /*for(int i = 1; i <= n; i++) {
168 printf("%d \n", str[i]);
169 }*/
170
171 /*puts("");
172 for(int i = 1; i <= tot; i++) {
173 printf("i = %d fail = %d | ", i, fail[i]);
174 for(int j = 0; j < 10; j++) {
175 printf("%d ", tr[i][j]);
176 }
177 puts("");
178 }*/
179
180 return 0;
181 }
AC代码
输出答案前如果不加那一句check(l)，会WA第二个点。