cf官方题解为数据结构维护贪心，时间复杂度$O(n^2logn)$。
但是这道题用wqs二分可以做到$O(nlog^2n)$。
第一次使用这个算法的时候甚至不知道它叫wqs二分。
有关wqs二分->wqs本人的课件
容易想到此题的$O(nab)$的做法,就是暴力dp。
暴力dp:
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
double p[2010],q[2010],dp[510][510][510];//dp[i][j][k]表示前i个神奇宝贝使用了j个精灵球和k个超级球
int 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]);
}
for(int i=1;i<=n;i++){
for(int j=0;j<=a;j++){
for(int k=0;k<=b;k++){
dp[i][j][k]=0;
if(max(j,k)>n){
continue;
}
dp[i][j][k]=dp[i-1][j][k];
if(j!=0){
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]+p[i]);
}
if(k!=0){
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]+q[i]);
}
if(j!=0&&k!=0){
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-1]+p[i]+q[i]-p[i]*q[i]);
}
}
}
}
printf("%.10lf
",dp[n][a][b]);
return 0;
}
我们考虑优化这个DP。
首先要优化状态，因为它本身三维状态。
我们试着不考虑a的限制，设状态$dp_{i,j}$表示前i个神奇宝贝，使用j个超级球和若干精灵球的最大期望。
但是这样可能会多用一些精灵球。于是我们假设每次使用一个精灵球，需要花费一个代价$ca$，并在dp时记录精灵球的用量，设为$ua$。那么实际期望就是$dp_{i,b}+ua_n imes ca$。
那么如何使它刚好使用a个精灵球呢？
发现精灵球用量随ca的增加而不增(不一定降)。
没错，二分ca。
于是,复杂度从$O(n3)$下降为$O(n2logn)$，已经可以过了。
这就是wqs二分，二分一个附加费用使某一物品的使用量发生变化。
但是还可以优化。
既然a这一维可以被省略，b这一维为什么不可以呢？
于是我们用同样的方法设$dp_i$为前i只神奇宝贝，使用若干精灵球和超级球的期望，二分使用超级球的代价$cb$并记录dp过程中超级球的使用量$ub$。
那么，实际代价就是$dp_n+ua_n imes ca+ub_n imes cb$
代码:
#include<bits/stdc++.h>
using namespace std;
const double _=1e-10;
int n,a,b,numa[100010],numb[100010];
double p[100010],q[100010],dp[100010];
void Check(double ca,double cb){//当使用精灵球的代价为ca,超级球为cb时的期望
for(int i=1;i<=n;i++){
dp[i]=0;
numa[i]=0;
numb[i]=0;
dp[i]=dp[i-1];
numa[i]=numa[i-1];
numb[i]=numb[i-1];
if(dp[i]<dp[i-1]+p[i]-ca-_){//注意精度
dp[i]=dp[i-1]+p[i]-ca;
numa[i]=numa[i-1]+1;
numb[i]=numb[i-1];
}
if(dp[i]<dp[i-1]+q[i]-cb-_){
dp[i]=dp[i-1]+q[i]-cb;
numa[i]=numa[i-1];
numb[i]=numb[i-1]+1;
}
if(dp[i]<dp[i-1]+p[i]-ca+q[i]-cb-p[i]*q[i]-_){
dp[i]=dp[i-1]+p[i]-ca+q[i]-cb-p[i]*q[i];
numa[i]=numa[i-1]+1;
numb[i]=numb[i-1]+1;
}
}
}
double check(double co){
double l=0,r=1,mid;//二分cb
for(int i=1;i<=50;i++){//同二分ca的过程
mid=(l+r)/2;
Check(co,mid);
if(numb[n]>b){
l=mid;
}else{
r=mid;
}
}
return l;
}
double l,r,mid,v,ans;
int 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]);
}
l=0;
r=1;//二分ca
for(int i=1;i<=50;i++){//由于实数二分所以二分固定次数即可
mid=(l+r)/2;
v=check(mid);
if(numa[n]>a){//用量大于a,增大ca
l=mid;
}else{//否则减小ca
r=mid;
}
}
Check(l,v);
printf("%.5lf
",dp[n]+l*a+v*b);
return 0;
}