P5308 [COCI2019] Quiz
可以发现是一个凸函数。不考虑 $k$ ，可以得到 DP 方程。记 $f _ i$ 表示还剩 $i$ 个人的最大奖励。
$$
f _ i = \min _ {j < i} f _ j + \frac {i - j} i
$$
考虑斜率优化。注意，这里是分式，和一般的斜率优化的式子不一样。若 $j$ 处转移比 $k$ 处转移更优，则
$$
\begin {array} {c}
f _ j + \frac {i - j} i > f _ k + \frac {i - k} i \\
f _ j - f _ k > \frac {j - k} i \\
\frac {f _ j - f _ k} {j - k} > \frac 1 i
\end {array}
$$
一个点即 $(a, f _ a) $ ，斜率为 $k = \frac 1 i$ 。适用斜率优化。
查看代码
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
| #include <cstdio>
using namespace std;
double eps = 1e-12;
const int N = 1e5 + 10;
int n, m, cnt[N];
double f[N];
int hd, tl, q[N];
double slp(int a, int b)
{
return (f[a] - f[b]) / (a - b);
}
void check(double x)
{
hd = 1, tl = 0;
q[++tl] = 0;
for (int i = 1; i <= n; i++)
{
while (hd < tl && slp(q[hd], q[hd + 1]) > 1.0 / i)
hd++;
cnt[i] = cnt[q[hd]] + 1;
f[i] = f[q[hd]] + (double)(i - q[hd]) / i - x;
while (hd < tl && slp(q[tl - 1], q[tl]) < slp(q[tl], i))
tl--;
q[++tl] = i;
}
}
int main()
{
scanf("%d%d", &n, &m);
check(0);
double l = 0, r = 1, res;
while (r - l > eps)
{
double mid = (l + r) / 2;
check(mid);
cnt[n] <= m ? (res = f[n] + mid * m, r = mid) : l = mid;
}
printf("%.9lf", res);
return 0;
}
|