传送门：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]了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #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 mpconst 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;} |