[CF739E]Gosha is hunting

DP 二分 贪心 堆

题面

现在一共有$N$只神奇宝贝。 你有$a$个宝贝球和$b$个超级球。
宝贝球抓到第$i$只神奇宝贝的概率是 $p_i$​ ，超级球抓到的概率则是$u_i$。
不能往同一只神奇宝贝上使用超过一个同种的球，但是可以往同一只上既使用宝贝球又使用超级球（都抓到算一个）。
请合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。

• $n\leq2000$

解析

这题讲课时有一种贪心做法。
先按超级球捕捉概率排序。
二分最后一次用超级球的位置，则前面要不$p+u$，要不$p$；后面要不$p$，要不$0$。
这样就可以拿个堆贪心地选取以最大化期望。

看到这题，裸$DP$是三维的。
设$f[i][j][k]$表示到第$i$个宝贝，用$j$个宝贝球，$k$个超级球的期望。
然而$O(n^3)$没分。

以下摘自巨佬yyb的博客
发现可以凸优化，对于其中一个球给它二分一个权值，表示每使用一次就需要额外花费掉这么多的权值，同时不再限制使用的个数。
然后忽略这一个限制，做$dp$，利用最优解使用的这种球的个数以及限制个数继续二分。
两维都可以这么做，复杂度$O(nlog^2n)$。

怎么说呢，通过二分强加权值来代替限制这个操作好像出现不止一次了。例如[国家集训队2]Tree I。
知识学不学得会是一回事，会不会灵活运用又是一回事。。。

还有个细节，如果要嵌套二分，精度要求$(eps)$要翻倍。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#define ll long long
#define re register
#define il inline
#define db double 
#define eps 1e-8
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=5e3+100;
int n,ta,tb;
db f[N],fa[N],fb[N];
struct dat{db a,b;}t[N];
il void check(re db w1,re db w2)
{
  fp(i,1,n)
    {
      f[i]=f[i-1];fa[i]=fa[i-1];fb[i]=fb[i-1];
      if(f[i-1]+t[i].a-w1>f[i]) f[i]=f[i-1]+t[i].a-w1,fa[i]=fa[i-1]+1,fb[i]=fb[i-1];
      if(f[i-1]+t[i].b-w2>f[i]) f[i]=f[i-1]+t[i].b-w2,fa[i]=fa[i-1],fb[i]=fb[i-1]+1;
      if(f[i-1]+t[i].a+t[i].b-t[i].a*t[i].b-w1-w2>f[i]) f[i]=f[i-1]+t[i].a+t[i].b-t[i].a*t[i].b-w1-w2,fa[i]=fa[i-1]+1,fb[i]=fb[i-1]+1;
    }
}
int main()
{
  ios::sync_with_stdio(false);
  cin>>n>>ta>>tb;
  fp(i,1,n) cin>>t[i].a;
  fp(i,1,n) cin>>t[i].b;
  re db l1=0,r1=1,mid1,l2,r2,mid2;
  while(l1+eps<r1)
    {
      mid1=(l1+r1)/2;
      l2=0,r2=1;
      while(l2+eps<r2)
    {
      mid2=(l2+r2)/2;
      check(mid1,mid2);
      if(fb[n]>tb) l2=mid2;else r2=mid2;
    }
      check(mid1,r2);
      if(fa[n]>ta) l1=mid1;else r1=mid1;
    }
  check(r1,r2);
  printf("%.4lf\n",f[n]+r1*ta+r2*tb);
  return 0;
}