CF739E Gosha is hunting

传送门：http://codeforces.com/contest/739/problem/E

题意：n个小精灵，a个宝贝球，b的大师球，每个小精灵可以用宝贝球或大师球或两个球捕捉，成功概率为$p_i,u_i$求期望最大捕捉数

非常厉害而且有趣的做法

考虑一个凸函数$f(x)$，现在有一个黑箱可以求它的极大值点,那么如何计算任意一个点$f(x_0)$的值?
构造函数$F(x)=f(x)-kx$,显然F也是凸函数，并且我们假设也能求它的极大值点，而且注意到k越大，极大值点就会越向左移
那么就可以二分k，使得$F(x)$的极大值点为$x_0$,就得到了$f(x_0)=F(x_0)+kx_0$
回到原问题，我们令$f[i][j](k)$表示前i个点用j个宝贝球k个大师球的期望，显然关于k这个函数是凸函数
按照上述方法就可以快速求出f[n][a][b]了

#include<bits/stdc++.h>
using namespace std;
const int maxn=2020;

int n,a,b;
double p[maxn],u[maxn];
double f[maxn][maxn];
int g[maxn][maxn];
#define make_pair mp
const double eps=1e-10;
void update(double &t,int &x,double f,int y){
	if(f>t+eps){
		t=f;
		x=y;
	}
}

void calc(double k){
	for(int i=1;i<=n;i++){
		for(int j=0;j<=a;j++){
			f[i][j]=0;
			g[i][j]=0;
			
			update(f[i][j],g[i][j],f[i-1][j],g[i-1][j]);
			update(f[i][j],g[i][j],f[i-1][j]+u[i]-k,g[i-1][j]+1);
			if(j)update(f[i][j],g[i][j],f[i-1][j-1]+p[i],g[i-1][j-1]);
			if(j)update(f[i][j],g[i][j],f[i-1][j-1]+1-(1-p[i])*(1-u[i])-k,g[i-1][j-1]+1);
		}
	}
}

int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)cin>>p[i];
	for(int i=1;i<=n;i++){
		cin>>u[i];
		//u[i]=1;
	}
	
	double l=0,r=1e9;
	int T=100;
	double ansf;
	while(T--){
		double mid=(l+r)/2;
		calc(mid);
		if(g[n][a]<=b)
			r=mid;
		else
			l=mid;
	}
	
	calc(l);
	
	printf("%.8f\n",f[n][a]+b*l);
	return 0;
}