法一：
匹配问题，网络流！
最大费用最大流，S到A，B流a/b费0，A，B到i流1费p[i]/u[i]，同时选择再减p[i]*u[i]?
连二次！所以i到T流1费0流1费-p[i]*u[i]
最大流由于ab都选择完最优
最大费用，所以不会第一次走-p[i]*u[i]
法二：
DP怎么写？
dp[i][j][k]
优化？
一定选择a、b个！
恰好选择a、b个？
WQS二分！
一定是满足凸函数的性质的
所以选择若干个a，代价ca，求dp[i][b]
再次WQS二分！
所以选择若干个a,b，代价ca，cb,求dp[i]
O(nlog^2n)
卡精度
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define num (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=num;isdigit(ch=getchar());x=x*+num);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}
template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');} namespace Miracle{
const int N=;
const double eps=1e-;
int numa[N],numb[N];
int n,a,b;
double p[N],u[N];
double dp[N];
void wrk(double ca,double cb){
for(reg i=;i<=n;++i){
dp[i]=dp[i-];numa[i]=numa[i-];numb[i]=numb[i-];
if(dp[i]<dp[i-]+p[i]-ca-eps){
dp[i]=dp[i-]+p[i]-ca;numa[i]=numa[i-]+;numb[i]=numb[i-];
}
if(dp[i]<dp[i-]+u[i]-cb-eps){
dp[i]=dp[i-]+u[i]-cb;numb[i]=numb[i-]+;numa[i]=numa[i-];
}
if(dp[i]<dp[i-]+u[i]+p[i]-p[i]*u[i]-ca-cb-eps){
dp[i]=dp[i-]+u[i]+p[i]-p[i]*u[i]-ca-cb;numb[i]=numb[i-]+;numa[i]=numa[i-]+;
}
}
}
double che(double ca){
double l=,r=;
for(reg i=;i<=;++i){
double mid=(l+r)/;
wrk(ca,mid);
if(numb[n]>b){
l=mid;
}else{
r=mid;
}
}
return (l+r)/;
}
int main(){
rd(n);rd(a);rd(b);
for(reg i=;i<=n;++i){
scanf("%lf",&p[i]);
}
for(reg i=;i<=n;++i){
scanf("%lf",&u[i]);
}
double l=,r=,ka,kb;
for(reg i=;i<=;++i){
double mid=(l+r)/;
kb=che(mid);
if(numa[n]>a){
l=mid;
}else{
r=mid;
}
}
ka=(l+r)/;
wrk(ka,kb);
printf("%.10lf",dp[n]+ka*a+kb*b);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/3/22 20:22:58
*/
巧妙之处：虽然不是恰好选择，但是选择a，b个一定是最优的！（就算是区间，也可以区间WQS二分）