【CF739E】Gosha is hunting（动态规划，凸优化）

题面

洛谷

CF

题解

一个\(O(n^3)\)的\(dp\)很容易写出来。

我们设\(f[i][a][b]\)表示前\(i\)个怪，两种球用了\(a,b\)个的最大期望，

直接用概率转移就好了。然而这样子会TLE飞。

发现可以凸优化，对于其中一个球给它二分一个权值，表示每使用一次就需要额外花费掉这么多的权值，同时不再限制使用的个数。

然后忽略这一个限制，做\(dp\)，利用最优解使用的这种球的个数以及限制个数继续二分。

两维都可以这么做，复杂度\(O(nlog^2)\)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define MAX 2020

#define eps 1e-8

#define cmax(x,y) (x=(x<y?y:x))

double p[MAX],u[MAX];

double f[MAX],fa[MAX],fb[MAX];

int n,a,b;

void Calc(double w1,double w2)

{

	for(int i=1;i<=n;++i)

	{

		f[i]=f[i-1];fa[i]=fa[i-1];fb[i]=fb[i-1];

		if(f[i-1]+p[i]-w1>f[i])

			f[i]=f[i-1]+p[i]-w1,fa[i]=fa[i-1]+1,fb[i]=fb[i-1];

		if(f[i-1]+u[i]-w2>f[i])

			f[i]=f[i-1]+u[i]-w2,fa[i]=fa[i-1],fb[i]=fb[i-1]+1;

		if(f[i-1]+p[i]+u[i]-p[i]*u[i]-w1-w2>f[i])

			f[i]=f[i-1]+p[i]+u[i]-p[i]*u[i]-w1-w2,fa[i]=fa[i-1]+1,fb[i]=fb[i-1]+1;

	}

}

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",&u[i]);

	double l1=0,r1=1,l2,r2;

	while(l1+eps<=r1)

	{

		double mid1=(l1+r1)/2;

		l2=0;r2=1;

		while(l2+eps<=r2)

		{

			double mid2=(l2+r2)/2;

			Calc(mid1,mid2);

			if(fb[n]>b)l2=mid2;else r2=mid2;

		}

		Calc(mid1,r2);

		if(fa[n]>a)l1=mid1;else r1=mid1;

	}

	Calc(r1,r2);

	printf("%.6lf\n",f[n]+a*r1+b*r2);

	return 0;

}