menu ZigZagK的博客

正在努力加载中QAQ

[wqs二分套wqs二分]Codeforces739E【Gosha is hunting】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 21 次访问

题目概述

有 $n$ 个物品,可以用两种方式获得(可以一起用,一种获得了即可),两种方式成功的概率分别为 $a_i,b_i$ ,第一种方式可以用 $A$ 次,第二种方式可以用 $B$ 次。问获得物品的期望的最大值。

解题报告

神坑-1。很明显可以 $f_{i,j,k}$ 表示前 $i$ 个物品第一种方法用了 $j$ 次第二种方法用了 $k$ 次的最优解,但是这样是 $O(n^3)$ 的,要想办法优化。

转移和转移数都是 $O(1)$ 的,只能优化状态数了,于是想到wqs二分。因为用了越多收益越来越少(容易抓的都先用掉了),并且用越多越好,所以没毛病。砍掉一维之后变成 $O(n^2log_2n)$ ,可以过。

由于校内比赛时候出了这道题的加强版,所以继续想发现其实两维都可以砍掉,于是很愉快的做到 $O(nlog_2^2n)$ 。

示例程序

切记最后加上的一定是乘 $A$ 和乘 $B$ !

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
using namespace std;
typedef long double DB;
const int maxn=100000;

int n,A,B;DB a[maxn+5],b[maxn+5],f[maxn+5];pair<int,int> g[maxn+5];

inline void Fix(int i,DB F,int a,int b) {if (F>f[i]) f[i]=F,g[i].fr=a,g[i].sc=b;}
inline void DP(DB M,DB m){
    for (int i=1;i<=n;i++){
        f[i]=f[i-1];g[i]=g[i-1];
        Fix(i,f[i-1]+a[i]-M,g[i-1].fr+1,g[i-1].sc);
        Fix(i,f[i-1]+b[i]-m,g[i-1].fr,g[i-1].sc+1);
        Fix(i,f[i-1]+1-(1-a[i])*(1-b[i])-M-m,g[i-1].fr+1,g[i-1].sc+1);
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    while (~scanf("%d%d%d",&n,&A,&B)){
        for (int i=1;i<=n;i++) {double x;scanf("%lf",&x);a[i]=x;}
        for (int i=1;i<=n;i++) {double x;scanf("%lf",&x);b[i]=x;}
        DB L=0,R=1,l,r;
        for (DB M=(L+R)/2;R-L>1e-8;M=(L+R)/2){
            l=0;r=1;for (DB m=(l+r)/2;r-l>1e-8;m=(l+r)/2) DP(M,m),g[n].sc<=B?r=m:l=m;
            DP(M,r);g[n].fr<=A?R=M:L=M;
        }DP(R,r);printf("%.6f\n",double(f[n]+R*A+r*B));
    }return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up