CF739E Gosha is hunting —— WQS二分 套 WQS二分

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个神奇宝贝，$a$ 个宝贝球、$b$ 个超级球
    宝贝球抓到第 $i$ 个神奇宝贝的概率为 $p_i,$ 超级球为 $u_i$
    求最大期望个数

解题思路：

    很明显 $n^3$ 的 $dp$ 很蠢
    考虑到这里 恰好用 $b$ 个超级球 的要求
    则可以用套用 $WQS$ 二分
    求最大期望，则图形为上凸包
    注意由于 $dp$ 值为 $double$ ，所以枚举的斜率也必须为 $double$
    时间复杂度：$O(n^{2}logn)$

---

    定睛一看发现 $a$ 和 $b$ 都是同样的要求
    所以两者可以用 $WQS$ 二分优化
    时间复杂度：$O(nlo{g}^{2}n)$

---

    第一次感觉对二分一无所知。。。。
    这里套用两个二分的时候，精度要加倍
    而且判别的方式要特别注意
    我 $check$ 的满足需求是 $num[n]<=a/b$
    如果二分的边界判断不准确，是个很费脑的bug。。。
    有以下两种写法是可以正确处理到答案的：

double l1 = 0, r1 = 1.0, mid1, l2, r2, mid2;
while(r1 - l1 >= 0) {		// r1 - l1 > -eps
	mid1 = (l1 + r1) / 2;
	l2 = 0, r2 = 1.0;
	while(r2 - l2 >= 0){	// r2 - l2 > -eps
		mid2 = (l2 + r2) / 2;
		if(ck(mid1, mid2, 2)) r2 = mid2 - eps;	
		else l2 = mid2 + eps;		
	}
	if(ck(mid1, l2, 1)) r1 = mid1 - eps;	
	else l1 = mid1 + eps;	
}
ck(l1, l2, 1);
printf("%.5lf\n", dp[n] + l1 * a + l2 * b);

或者

double l1 = 0, r1 = 1.0, mid1, l2, r2, mid2;
while(r1 - l1 > eps) {		
	mid1 = (l1 + r1) / 2;
	l2 = 0, r2 = 1.0;
	while(r2 - l2 > eps){	
		mid2 = (l2 + r2) / 2;
		if(ck(mid1, mid2, 2)) r2 = mid2;
		else l2 = mid2;		
	}
	if(ck(mid1, r2, 1)) r1 = mid1;	
	else l1 = mid1;	
}
ck(r1, r2, 1);
printf("%.5lf\n", dp[n] + l1 * a + l2 * b);

---

一个 $WQS$二分

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 2e3 + 5;
const double eps = 1e-8;
int n, a, b, num[maxn][maxn];
double p[maxn], q[maxn], dp[maxn][maxn];

bool ck(double x) {
	double tmp;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=a; j++) {
			dp[i][j] = dp[i-1][j], num[i][j] = num[i-1][j];

			tmp = dp[i-1][j] + q[i] - x;
			if(tmp>dp[i][j] || (tmp==dp[i][j] && num[i-1][j]+1<num[i][j])) {
				dp[i][j] = tmp; num[i][j] = num[i-1][j] + 1;
			}
			if(j==0) continue;
			
			tmp = dp[i-1][j-1] + p[i];
			if(tmp>dp[i][j] || (tmp==dp[i][j] && num[i-1][j-1]<num[i][j])) {
				dp[i][j] = tmp; num[i][j] = num[i-1][j-1];
			}
			
			tmp = dp[i-1][j-1] + p[i] + q[i] - p[i]*q[i] - x;
			if(tmp>dp[i][j] || (tmp==dp[i][j] && num[i-1][j-1]+1<num[i][j])) {
				dp[i][j] = tmp; num[i][j] = num[i-1][j-1] + 1;
			}
		}
	}
	return num[n][a] <= b;
}

signed 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", q+i);
	double l = 0, r = 1.0, mid;
	while(r - l >= 0) {		// r - l > eps
		mid = (l + r) / 2;
		if(ck(mid)) r = mid - eps;	// r = mid
		else l = mid + eps;			// l = mid
	}
	ck(l);
	printf("%.4f\n", dp[n][a] + 1.0 * l * b);
}

---

$WQS$二分 套 $WQS$二分

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int maxn = 2e3 + 5;
const double eps = 1e-10;
int n, a, b, num1[maxn], num2[maxn];
double p[maxn], q[maxn], dp[maxn];

bool ck(double x, double y, int op) {
	double tmp;
	for(int i=1; i<=n; i++){
		dp[i] = dp[i-1], num1[i] = num1[i-1], num2[i] = num2[i-1];
		
		tmp = dp[i-1] + p[i] - x;
		if(tmp > dp[i]){
			dp[i] = tmp, num1[i] = num1[i-1] + 1, num2[i] = num2[i-1];
		}
		
		tmp = dp[i-1] + q[i] - y;
		if(tmp > dp[i]){
			dp[i] = tmp, num1[i] = num1[i-1], num2[i] = num2[i-1] + 1;
		}
		
		tmp = dp[i-1] + p[i] + q[i] - p[i] * q[i] - x - y;
		if(tmp > dp[i]){
			dp[i] = tmp, num1[i] = num1[i-1] + 1, num2[i] = num2[i-1] + 1;
		}
	}
	if(op == 1) return num1[n] <= a;
	else return num2[n] <= b;
}

signed 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", q+i);
	double l1 = 0, r1 = 1.0, mid1, l2, r2, mid2;
	while(r1 - l1 > eps) {		
		mid1 = (l1 + r1) / 2;
		l2 = 0, r2 = 1.0;
		while(r2 - l2 > eps){	
			mid2 = (l2 + r2) / 2;
			if(ck(mid1, mid2, 2)) r2 = mid2;
			else l2 = mid2;		
		}
		if(ck(mid1, r2, 1)) r1 = mid1;	
		else l1 = mid1;	
	}
	ck(r1, r2, 1);
	printf("%.5lf\n", dp[n] + r1 * a + r2 * b);
}