Luogu5308 [COCI2019] Quiz

tony102

2021 年 03 月 27 日

1776 次浏览

暂无评论

559字数

题解

[Link](https://www.luogu.com.cn/problem/P5308)

## Sol

正着 DP 好像不好表示这一次选的这一段，正难则反就倒着 DP。设 $f_i$ 表示从后往前的一轮还剩 $i$ 个人的最多奖金。暴力转移就是枚举下一轮还有 $j$ 人，即：

$$
f_i = max_{j<i} (f_j + \frac{i-j}{i} )
$$

有决策单调性，具体的，我们可以知道假如我们在将决策 $k$ 转移给了决策 $j$ ，其中 $k < j$ ，有

$$
f_k + \frac{i - k}{i} < f_j + \frac{i - j}{i}
$$

先由此证明决策是单调的，已知 $f_i$ 要尽可能大。同时，$i$ 增加时 $\frac{1}{i}$ 是在不断减小，说明 $f$ 是一个关于 $i$ 的上凸函数。继续化简式子，

$$
f_j - f_k > \frac{j - k}{i}
$$

$$
\frac{f_j-f_k}{j - k} > \frac{1}{i}
$$

我们可以二分切这个上凸函数的斜率。也就是说，我们可以二分 $\frac{1}{i}$ 切这个上凸壳 $f_j$ 的一条直线的斜率，把 $f_i$ 作为截距。然后做斜率优化即可。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e5 + 5;

int n, k;
int q[SIZE], cnt[SIZE];
double f[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

double slope(int i, int j) { 
	return (f[i] - f[j]) / (double) (i - j);
}

int judge(double mid) {
	int head = 1, tail = 1; q[head] = 0;
	for (int i = 1; i <= n; ++ i) {
		while (head < tail && slope(q[head], q[head + 1]) > 1.00 / i) ++ head;
		f[i] = f[q[head]] + (i - q[head]) * 1.00 / i - mid, cnt[i] = cnt[q[head]] + 1;
		while (head < tail && slope(q[tail - 1], q[tail]) < slope(q[tail], i)) -- tail;
		q[++ tail] = i;
	}
	return cnt[n] >= k;
}

int main() {
	n = read(), k = read();
	double l = -1, r = SIZE - 5, mid = 0;
	for (int i = 1; i <= 100; ++ i) {
		mid = (l + r) / 2.000;
		if (judge(mid)) l = mid;
		else r = mid;
	}
	judge(l);
	printf("%.9lf\n", f[n] + (double) mid * k);
	return 0;
}
```

最后修改：2023 年 07 月 19 日