题目地址
题意：
现在一共有 \(n\) 只神奇宝贝。
你有 \(a\) 个『宝贝球』和 \(b\) 个『超级球』。
『宝贝球』抓到第 \(i\) 只神奇宝贝的概率是 \(p_i\)，『超级球』抓到的概率则是 \(u_i\)。
不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。
请合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。
\(n \leq 2000\)。
分析：
一开始陷入误区：我令每个B元素的贡献值减去mid，以此来约束B的选取数量。然而这样做的话，只需要选择所有贡献大于0的B即可，而且最后也不能通过将截距加上k*b来计算真实结果（也就是，这时的“切线”不是一条直线！）。
真正的做法应该是：每选取一个指定的元素，最终的结果都要减去mid，依次来约束选取数量。这和上一种定义是截然不同的，我们不能贪心地选取B，而必须进行动态规划。联想一下tree那道题，对那题而言无论哪种定义，结果都是一样的，所有才能把开销直接附加在贡献值上。
wqs二分需要在贡献相同的情况下，规定尽量多选和尽量少选。因此每个属性都要定义偏序关系。
在偏序关系上，我尚不太理解这一题。这是对标准代码的解释：
要确定过程中是尽量用更少的球还是更多的球，这样二分时才能在多点共线的情况下确定如何调整并记录答案
这里写的是尽量用更少的球，也就是小于号（不取等），实际上另一种也可以，不过二分里面就要改
但我并没有想明白，这样在check中是如何保证这样的偏序关系的。
个人猜测，由于我固定了每次check的转移顺序（无论if的具体顺序），因此最后实际上具备了偏序关系（我们要保证的，无非就是当斜率增大时，切点横坐标一定随之增大或减小）。
在应用wqs二分套wqs二分时，我发现：
if(mid<=a) l=mid; else r=mid;
对于上式，目的就是取得a这个值，但有时用<时取r，和用<=取l，结果居然不一样（我有30%的把握怀疑，这就是因为偏序关系模糊导致的）。
这个问题，我是这样解决的：对于内部的wqs二分，当其取得a时，便立即退出。
if(mid==a)
break;
对外部的也可以，或者说，对wqs二分，达到指定值后就可以退出，因为共线的点的真实值是可以由斜截式直接算出来的。
另外，wqs二分套wqs二分，所需的精度会升级，这里我开了1e-8。
代码：
\(O(n^2logn)\)：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2005;
const double eps=1e-6;
int n,a,b;
double p[maxn],q[maxn];
double res;
double dp[maxn][maxn];
int cnt[maxn]; //用cnt滚动地记录转移时的约束使用数量
int check(double x)
{
for(int i=0;i<=a;++i)
cnt[i]=0;
for(int i=1;i<=n;++i)
{
for(int j=a;j>=0;--j)
{
dp[i][j]=dp[i-1][j];
if(dp[i][j]<=dp[i-1][j]+q[i]-x){
dp[i][j]=dp[i-1][j]+q[i]-x;
cnt[j]=cnt[j]+1;
}
if(j==0) continue;
if(dp[i][j]<=dp[i-1][j-1]+p[i]){
dp[i][j]=dp[i-1][j-1]+p[i];
cnt[j]=cnt[j-1];
}
if(dp[i][j]<=dp[i-1][j-1]+p[i]+q[i]-p[i]*q[i]-x){
dp[i][j]=dp[i-1][j-1]+p[i]+q[i]-p[i]*q[i]-x;
cnt[j]=cnt[j-1]+1;
}
}
}
res=dp[n][a];
// cout<<x<<" "<<cnt[a]<<" "<<res<<endl;
return cnt[a];
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cin>>n>>a>>b;
for(int i=1;i<=n;++i) cin>>p[i];
for(int i=1;i<=n;++i) cin>>q[i];
double l=-1,r=1;
while(r-l>eps)
{
double mid=(r+l)/2;
if(check(mid)<=b)
r=mid;
else
l=mid;
}
check(r);
cout<<fixed<<setprecision(6)<<res+r*b;
}
\(O(n(logn)^2)\) wqs二分套wqs二分
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=2005;
const double eps=1e-8;
int n,a,b;
double p[maxn],q[maxn];
double res;
double dp[maxn];
pair<int,int> check(double x,double y)
{
int ca=0,cb=0;
for(int i=1;i<=n;++i)
{
dp[i]=dp[i-1];
int ta=ca,tb=cb;
if(dp[i]<dp[i-1]+p[i]-x){
dp[i]=dp[i-1]+p[i]-x;
ta=ca+1; tb=cb;
}
if(dp[i]<dp[i-1]+q[i]-y){
dp[i]=dp[i-1]+q[i]-y;
tb=cb+1; ta=ca;
}
if(dp[i]<dp[i-1]+p[i]+q[i]-p[i]*q[i]-x-y){
dp[i]=dp[i-1]+p[i]+q[i]-p[i]*q[i]-x-y;
ta=ca+1; tb=cb+1;
}
ca=ta;
cb=tb;
}
res=dp[n];
return {ca,cb};
}
int main()
{
cin.tie(0)->sync_with_stdio(false);
cin>>n>>a>>b;
for(int i=1;i<=n;++i) cin>>p[i];
for(int i=1;i<=n;++i) cin>>q[i];
double la=-1,ra=1;
double lb=-1,rb=1;
pair<int,int> ret;
while(ra-la>eps)
{
double ma=(ra+la)/2;
lb=-1,rb=1;
while(rb-lb>eps)
{
double mb=(rb+lb)/2;
ret=check(ma,mb);
if(ret.second>=b)
lb=mb;
else
rb=mb;
if(ret.second==b)
break;
}
if(ret.first>=a)
la=ma;
else
ra=ma;
}
check(la,lb);
cout<<fixed<<setprecision(6)<<res+la*a+lb*b;
}