【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;
}

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