题解 CF739E 【Gosha is hunting】

· · 题解

1. O(n^3) 暴力DP

通过题意可设出dp数组定义， f[i][j][k] 表示第i只pokemon，已用了j个a球，

k个b球的最优期望。简单转移即可。

#include<bits/stdc++.h>
#define re register
using namespace std;
int n,a,b;
double p[100010],q[100010];
double f[3][1001][1001];
signed main(){
   while(~scanf("%d",&n)){
   scanf("%d%d",&a,&b);re double ans=0.0;re int now=0,pre;
   for(re int i=1;i<=n;++i) scanf("%lf",&p[i]);
   for(re int i=1;i<=n;++i) scanf("%lf",&q[i]);
   for(re int i=0;i<=a;++i) for(re int j=0;j<=b;++j) f[now][i][j]=0.0;
   for(re int i=1;i<=n;++i){ pre=now;now^=1;
   for(re int j=0;j<=a;++j) for(re int k=0;k<=b;++k){ 
       f[now][j][k]=f[pre][j][k];
       if(k)f[now][j][k]=max(f[now][j][k],f[pre][j][k-1]+q[i]);
       if(j)f[now][j][k]=max(f[now][j][k],f[pre][j-1][k]+p[i]);
       if(j&&k)f[now][j][k]=max(f[now][j][k],f[pre][j-1][k-1]+p[i]+q[i]-p[i]*q[i]);
   }   }
   for(re int i=0;i<=a;++i) for(re int j=0;j<=b;++j) ans=max(f[now][i][j],ans);
   printf("%.5lf\n",ans);
   }
}

2. O(n^2logn) 最大费用最大流

观察题面，可知，通过a,b个数限制流量，以p[i],q[i]为费用，-p[i]*q[i] 修正费用即可。

给一只pokemon分配一个a球可以得到p[i]的收益，给一只pokemon分配一个b球可以得到q[i]的收益,但同时分配这两种食品将损失p[i]*q[i]的收益.如果不考虑p[i]*q[i]的损失，有一个很明显的费用流建图:建两个点表示a球和b球，从原点向这两个点分别连费用为0,流量等于对应食品数目的边，从a球向每只pokemon连流量为1,费用为p[i]的边，从b球向每只pokemon连流量为1,费用为q[i]的边,从每只pokemon向汇点连流量为2,费用为0的边。

那么p[i]*q[i]的损失应当可以加到这个比较简单的模型的某一条边上。我们把从pokemon连向汇点的边拆成两条，流量均为1,但一条费用为0,一条费用为-p[i]*q[i],这样跑出来就是对的.

#include<bits/stdc++.h>
#define re register
#define inf 0x7fffffff
using namespace std;
int n,a,b,st,p,q,ed,tot=1,first[100010];
int flow[100010],pre[100010];bool flag=0;
double pp[100010],qq[100010],dis[100010],ans;
bool inq[100010];
struct node{int u,v,fl,val,next;double cst;}edge[800010];
inline void add(int x,int y,int fl,double cst){
    edge[++tot].v=y;
    edge[tot].u=x;
    edge[tot].val=0;
    edge[tot].fl=fl;
    edge[tot].cst=cst;
    edge[tot].next=first[x];
    first[x]=tot;
}
inline void spfa(){
    queue<int> q; q.push(st),dis[st]=0.0,flow[st]=inf;
    while(q.size()){
        re int x=q.front();q.pop(),inq[x]=0;
        for(re int i=first[x];i;i=edge[i].next){
            re int y=edge[i].v;re double w=edge[i].cst;
            if(dis[y]<dis[x]+w&&edge[i].val<edge[i].fl){
                dis[y]=dis[x]+w,pre[y]=i;
                flow[y]=min(flow[x],edge[i].fl-edge[i].val);
                if(!inq[y]) q.push(y),inq[y]=1;
            }
        }
    }
}
inline void work(){
    for(re int i=0;i<=n+10;++i)
        flow[i]=pre[i]=0,dis[i]=-8848488.0;
    spfa(); if(dis[ed]<0) flag=1;
    else{
        for(re int i=ed;i!=st;i=edge[pre[i]].u)
        edge[pre[i]].val+=flow[ed],edge[pre[i]^1].val-=flow[ed];
        ans+=dis[ed];
    }
}
signed main(){
    scanf("%d%d%d",&n,&a,&b)ans=0.0;
    for(re int i=1;i<=n;++i) scanf("%lf",&pp[i]);
    for(re int i=1;i<=n;++i) scanf("%lf",&qq[i]);
    st=0,p=n+1,q=n+2,ed=n+3;
    tot=1; memset(first,0,sizeof(first));
    add(st,p,a,0);add(p,st,0,0);
    add(st,q,b,0);add(q,st,0,0);
    for(re int i=1;i<=n;++i){
        add(p,i,1,pp[i]),add(i,p,0,-pp[i]);
        add(q,i,1,qq[i]),add(i,q,0,-qq[i]);
        add(i,ed,1,-pp[i]*qq[i]);
        add(ed,i,0,pp[i]*qq[i]);
        add(i,ed,1,0);add(ed,i,0,0);
    }flag=0;
    while(!flag) work();
    printf("%.5lf\n",ans);
}

3.O(nlog^2n) wqs二分套wqs二分（凸优化DP）

我们首先不考虑b的限制,假设b球可以任意使用，定义f[i][j]表示前i只pokemon使用j包a球和若干包b球得到的最大收益。直接这么DP会n只pokemon都用b球，可能会超出b的限制。

为了减少b球的使用,我们可以假定使用一个b球需要额外付出cost的代价(也就是在转移的时候如果一只pokemon用了b球,它对期望值的贡献要减去cost).在DP的时候,求解出f[i][j]的最大值,并记录最优方案中b球使用的数目x,那么此时真实的期望是f[i][j]的最优值加上x*cost,这个结果必然也是用了x个b球时能够得到的最优结果.

但是,如果我们随便假定一个cost去跑DP,得到的方案并不一定把所有b球都用完,我们需要一个能把所有b球都用完的cost的值.

显然b球使用量随着 cost的变化是单调变化的,我们可以二分cost的数值.

时间复杂度O(n^2logn)

考虑进一步优化，a球的cost也同样可以利用wqs二分处理，故采用二分套二分的形式，将时间复杂度优化到O(nlog^2n).

#include<bits/stdc++.h>
#define re register
#define eps 1e-8
using namespace std;
int n,a,b; double ans,l1,r1,l2,r2,mid1,mid2;
double f[100010],p[100010],pp[100010],q[100010],qq[100010];
inline bool solp(re double x,re double y){
    for(re int i=1;i<=n;++i){
        f[i]=f[i-1],p[i]=p[i-1],q[i]=q[i-1];
        if(f[i-1]+pp[i]-x>f[i])
            f[i]=f[i-1]+pp[i]-x,p[i]=p[i-1]+1,q[i]=q[i-1];
        if(f[i-1]+qq[i]-y>f[i])
            f[i]=f[i-1]+qq[i]-y,p[i]=p[i-1],q[i]=q[i-1]+1;
        if(f[i-1]+pp[i]+qq[i]-pp[i]*qq[i]-x-y>f[i])
            f[i]=f[i-1]+pp[i]+qq[i]-pp[i]*qq[i]-x-y,p[i]=p[i-1]+1,q[i]=q[i-1]+1;
    }
    return p[n]>a;
}
inline bool solq(re double x,re double y){
    for(re int i=1;i<=n;++i){
        f[i]=f[i-1],p[i]=p[i-1],q[i]=q[i-1];
        if(f[i-1]+pp[i]-x>f[i])
            f[i]=f[i-1]+pp[i]-x,p[i]=p[i-1]+1,q[i]=q[i-1];
        if(f[i-1]+qq[i]-y>f[i])
            f[i]=f[i-1]+qq[i]-y,p[i]=p[i-1],q[i]=q[i-1]+1;
        if(f[i-1]+pp[i]+qq[i]-pp[i]*qq[i]-x-y>f[i])
            f[i]=f[i-1]+pp[i]+qq[i]-pp[i]*qq[i]-x-y,p[i]=p[i-1]+1,q[i]=q[i-1]+1;
        }
    return q[n]>b;
}
inline void solve(re double x,re double y){
    for(re int i=1;i<=n;++i){
        f[i]=f[i-1],p[i]=p[i-1],q[i]=q[i-1];
        if(f[i-1]+pp[i]-x>f[i])
            f[i]=f[i-1]+pp[i]-x,p[i]=p[i-1]+1,q[i]=q[i-1];
        if(f[i-1]+qq[i]-y>f[i])
            f[i]=f[i-1]+qq[i]-y,p[i]=p[i-1],q[i]=q[i-1]+1;
        if(f[i-1]+pp[i]+qq[i]-pp[i]*qq[i]-x-y>f[i])
            f[i]=f[i-1]+pp[i]+qq[i]-pp[i]*qq[i]-x-y,p[i]=p[i-1]+1,q[i]=q[i-1]+1;
    }
}
signed main(){
    scanf("%d%d%d",&n,&a,&b);
    ans=0.0,l1=0.0,r1=1.0,l2=0.0,r2=1.0;
    for(re int i=1;i<=n;++i) scanf("%lf",&pp[i]);
    for(re int i=1;i<=n;++i) scanf("%lf",&qq[i]);
    while(r1-l1>eps){
        mid1=(l1+r1)/2.0;
        l2=0.0,r2=1.0;
        while(r2-l2>eps){
            mid2=(l2+r2)/2.0;
            if(solq(mid1,mid2)) l2=mid2;
            else r2=mid2;
        }
        if(solp(mid1,r2)) l1=mid1;
        else r1=mid1;
    }
    solve(r1,r2); ans=f[n]+a*r1+b*r2;
    printf("%.5lf\n",ans);
}