CF739E Gosha is hunting

博主： tony102
发布时间：2021 年 03 月 27 日
1852 次浏览
暂无评论
2070字数
分类：题解

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

## Sol

首先使用精灵球抓到第 $i$ 只宝可梦的概率是 $p_i$ ， 大师球抓到第 $i$ 只宝可梦的概率是 $u_i$ ，两种球一起用的抓到的概率就是 $p_i + u_i - p_i \times u_i$

~~（话说这玩意儿我小时候叫做神奇宝贝后来就变成了英文音译的宝可梦，再早一点的版本又叫做口袋妖怪（精灵）~~

那么我们考虑暴力 DP ，设 $f_{i,j,k}$ 表示抓前 $i$ 只宝可梦用了 $j$ 个精灵球和 $k$ 个大师球的最大期望，转移很简单，是:

$$
f_{i,j,k} = max\left\{ f_{i-1,j,k}, f_{i-1, j-1, k} + p_i, f_{i-1,j,k-1} +u_i, f_{i-1,j-1,k-1} + p_i + u_i - p_i \times u_i\right\}
$$

那么这样是 $\Theta(n^3)$ 的，显然无法通过。但是如果我们没有恰好 $k$ 个球的限制，就非常好做。一般有这种字眼的都可以考虑WQS二分（二分一个附加权值）来优化 DP， 这其实也是决策单调性与凸优化。

可以发现这玩意儿转移的位置是单调的，也就是说满足决策单调性，决策单调性与凸性有一定的关联。在这道题目中, $f_{i,j,k}$ 是一个既满足在 $j$ 维上是一个上凸的函数，也满足在 $k$ 维上是一个上凸的函数。我们先来考虑一种情况，即先来看看在 $j$ 维上的情况。

对于有凸性的函数的单点求值可以考虑斜率凸优化,二分斜率 $mid$ 找到其在该凸壳上的切点,按照切点横坐标与目标的关系进行调整。具体的说，我们二分这个斜率切这个点的时候肯定不能切到凸壳上的每一个点，有的点可能是割线的关系（即截距 $> 0$ ) 。那么相当于给选这个点带来了一定的附加权值。所以，我们可以二分这个斜率，得到截距（附加权值），控制它恰好选 $k$ 次，减去的附加权值我们只要最后再给它加回来就可以了。

对于这道题，$j$ , $k$ 两维都满足这个性质，所以可以考虑两维都用 WQS 二分做掉。但是这个题目卡精度，简单卡过去的方法就是直接给定一个二分的次数，$eps$ 也要调一下。我在 vjudge 上交了好多发才卡过去。

其他例题推荐： [BZOJ2654 Tree](https://vjudge.net/problem/%E9%BB%91%E6%9A%97%E7%88%86%E7%82%B8-2654) (决策单调性与凸性，四边形不等式)  [Luogu5308 [COCI2019] Quiz](https://www.luogu.com.cn/problem/P5308) (决策单调性)

[Luogu5617 [MtOI2019]不可视境界线](https://www.luogu.com.cn/problem/P5617)

此外，证明决策单调性和凸性与四边形不等式相关。具体证明和做法就是 BZOJ2654 这道题

## Code

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

const int SIZE = 2e3 + 5;
const double eps = 1e-9;

int n, a, b;
int cnt1[SIZE], cnt2[SIZE];
double f[SIZE], p[SIZE], u[SIZE], mid1, mid2, L;

int dp() {
	f[0] = f[1] = 0.000, cnt1[0] = cnt1[1] = cnt2[0] = cnt2[1] = 0;
	for (int i = 1; i <= n; ++ i) {
		f[i] = f[i - 1], cnt1[i] = cnt1[i - 1], cnt2[i] = cnt2[i - 1];
		if (f[i - 1] + p[i] - mid1 - eps > f[i])
			f[i] = f[i - 1] + p[i] - mid1, cnt1[i] = cnt1[i - 1] + 1, cnt2[i] = cnt2[i - 1];
		if (f[i - 1] + u[i] - mid2 - eps > f[i])
			f[i] = f[i - 1] + u[i] - mid2, cnt1[i] = cnt1[i - 1], cnt2[i] = cnt2[i - 1] + 1;
		if (f[i - 1] + p[i] + u[i] - p[i] * u[i] - mid1 - mid2 - eps > f[i])
			f[i] = f[i - 1] + p[i] + u[i] - p[i] * u[i] - mid1 - mid2, cnt1[i] = cnt1[i - 1] + 1, cnt2[i] = cnt2[i - 1] + 1;
	}
	return cnt2[n] <= b;
}

int judge() {
	double l = 0.00, r = 1.00; 
	for (int i = 1; i <= 50; ++ i) {
		mid2 = (l + r) / 2.000;
		if (dp()) r = mid2;
		else l = mid2;
	}
	L = l;
	return cnt1[n] <= a;
}

int main() {
	scanf("%d %d %d", &n, &a, &b);
	for (int i = 1; i <= n; ++ i) scanf("%lf", &p[i]);
	for (int i = 1; i <= n; ++ i) scanf("%lf", &u[i]);
	double l = 0.0000, r = 1.0000;
	for (int i = 1; i <= 50; ++ i) {
		mid1 = (l + r) / 2.0000;
		if (judge()) r = mid1;
		else l = mid1;
	}
	printf("%.7lf\n", f[n] + l * (double) a + L * (double) b);
	return 0;
}
```

最后修改：2021 年 08 月 29 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rlenitkthe
真好呢
暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了

CF739E Gosha is hunting

tony102 • 2021 年 03 月 27 日

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

## Sol

首先使用精灵球抓到第 $i$ 只宝可梦的概率是 $p_i$ ， 大师球抓到第 $i$ 只宝可梦的概率是 $u_i$ ，两种球一起用的抓到的概率就是 $p_i + u_i - p_i \times u_i$

~~（话说这玩意儿我小时候叫做神奇宝贝后来就变成了英文音译的宝可梦，再早一点的版本又叫做口袋妖怪（精灵）~~

那么我们考虑暴力 DP ，设 $f_{i,j,k}$ 表示抓前 $i$ 只宝可梦用了 $j$ 个精灵球和 $k$ 个大师球的最大期望，转移很简单，是:

$$
f_{i,j,k} = max\left\{ f_{i-1,j,k}, f_{i-1, j-1, k} + p_i, f_{i-1,j,k-1} +u_i, f_{i-1,j-1,k-1} + p_i + u_i - p_i \times u_i\right\}
$$

[Luogu5617 [MtOI2019]不可视境界线](https://www.luogu.com.cn/problem/P5617)

此外，证明决策单调性和凸性与四边形不等式相关。具体证明和做法就是 BZOJ2654 这道题

## Code

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

const int SIZE = 2e3 + 5;
const double eps = 1e-9;

int n, a, b;
int cnt1[SIZE], cnt2[SIZE];
double f[SIZE], p[SIZE], u[SIZE], mid1, mid2, L;

int judge() {
	double l = 0.00, r = 1.00; 
	for (int i = 1; i <= 50; ++ i) {
		mid2 = (l + r) / 2.000;
		if (dp()) r = mid2;
		else l = mid2;
	}
	L = l;
	return cnt1[n] <= a;
}

CF739E Gosha is hunting

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

ARC125E Snack

Luogu4551 最长异或路径

Miscellaneous Math for CG 为计算机图形学准备的数学

Luogu6620 [省选联考 2020 A 卷] 组合数问题

20210916 2j0s1yydnnoat 模拟赛官方题解

CF739E Gosha is hunting

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CF739E Gosha is hunting

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款