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 > -epsmid1 = (l1 + r1) / 2;l2 = 0, r2 = 1.0;while(r2 - l2 >= 0){	// r2 - l2 > -epsmid2 = (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 > epsmid = (l + r) / 2;if(ck(mid)) r = mid - eps;	// r = midelse 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);
}