Tony102's Blog - 决策单调性
type: channel
link: https://tony102.com/index.php/tag/%E5%86%B3%E7%AD%96%E5%8D%95%E8%B0%83%E6%80%A7/
items: CF739E Gosha is hunting

CF739E Gosha is hunting
type: item
date: 2021-03-27T08:02:00+08:00
description: LinkSol首先使用精灵球抓到第 $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 (决策单调性与凸性，四边形不等式) [Luogu5308 [COCI2019] Quiz](https://www.luogu.com.cn/problem/P5308) (决策单调性)[Luogu5617 [MtOI2019]不可视境界线](https://www.luogu.com.cn/problem/P5617)此外，证明决策单调性和凸性与四边形不等式相关。具体证明和做法就是 BZOJ2654 这道题Code#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.0…