CF739E Gosha is hunting

2019/03/22 21:18
阅读数 13

法一:

匹配问题,网络流!

最大费用最大流,S到A,B流a/b费0,A,B到i流1费p[i]/u[i],同时选择再减p[i]*u[i]?

连二次!所以i到T流1费0流1费-p[i]*u[i]

最大流由于ab都选择完最优

最大费用,所以不会第一次走-p[i]*u[i]

 

法二:

DP怎么写?

dp[i][j][k]

优化?

一定选择a、b个!

恰好选择a、b个?

WQS二分!

一定是满足凸函数的性质的

所以选择若干个a,代价ca,求dp[i][b]

再次WQS二分!

所以选择若干个a,b,代价ca,cb,求dp[i]

O(nlog^2n)

卡精度

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define num (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=num;isdigit(ch=getchar());x=x*10+num);
    (fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Miracle{
const int N=2002;
const double eps=1e-10;
int numa[N],numb[N];
int n,a,b;
double p[N],u[N];
double dp[N];
void wrk(double ca,double cb){
    for(reg i=1;i<=n;++i){
        dp[i]=dp[i-1];numa[i]=numa[i-1];numb[i]=numb[i-1];
        if(dp[i]<dp[i-1]+p[i]-ca-eps){
            dp[i]=dp[i-1]+p[i]-ca;numa[i]=numa[i-1]+1;numb[i]=numb[i-1];
        }
        if(dp[i]<dp[i-1]+u[i]-cb-eps){
            dp[i]=dp[i-1]+u[i]-cb;numb[i]=numb[i-1]+1;numa[i]=numa[i-1];
        }
        if(dp[i]<dp[i-1]+u[i]+p[i]-p[i]*u[i]-ca-cb-eps){
            dp[i]=dp[i-1]+u[i]+p[i]-p[i]*u[i]-ca-cb;numb[i]=numb[i-1]+1;numa[i]=numa[i-1]+1;
        }
    }
}
double che(double ca){
    double l=0,r=1;
    for(reg i=1;i<=50;++i){
        double mid=(l+r)/2;
        wrk(ca,mid);
        if(numb[n]>b){
            l=mid;
        }else{
            r=mid;
        }
    }
    return (l+r)/2;
}
int main(){
    rd(n);rd(a);rd(b);
    for(reg i=1;i<=n;++i){
        scanf("%lf",&p[i]);
    }
    for(reg i=1;i<=n;++i){
        scanf("%lf",&u[i]);
    }
    double l=0,r=1,ka,kb;
    for(reg i=1;i<=50;++i){
        double mid=(l+r)/2;
        kb=che(mid);
        if(numa[n]>a){
            l=mid;
        }else{
            r=mid;
        }
    }
    ka=(l+r)/2;
    wrk(ka,kb);
    printf("%.10lf",dp[n]+ka*a+kb*b);
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2019/3/22 20:22:58
*/

 

巧妙之处:虽然不是恰好选择,但是选择a,b个一定是最优的!(就算是区间,也可以区间WQS二分)

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部