当前位置: 首页 > 工具软件 > WQS > 使用案例 >

【CF739E】Gosha is hunting(WQS二分套WQS二分)

狄冥夜
2023-12-01

点此看题面

大致题意: 你有两种捕捉球(分别为 A A A个和 B B B个),要捕捉 n n n个神奇宝贝,第 i i i个神奇宝贝被第一种球捕捉的概率是 s 1 i s1_i s1i,被第二种球捕捉的概率是 s 2 i s2_i s2i,问在最优策略下期望捕捉到的神奇宝贝数量。


W Q S WQS WQS二分

这应该是一道比较经典的 W Q S WQS WQS二分题(毕竟是 W Q S WQS WQS二分套 W Q S WQS WQS二分)。

L i n k Link Link

W Q S WQS WQS二分 详见博客 WQS二分学习笔记


W Q S WQS WQS二分套 W Q S WQS WQS二分

如果你知道 W Q S WQS WQS二分,应该就不难想到 W Q S WQS WQS二分一个代价 C 1 C1 C1,表示每使用一个第一种球所需要的代价,然后再 W Q S WQS WQS二分一个代价 C 2 C2 C2,表示每使用一个第二种球所需要的代价。于是就成了 W Q S WQS WQS二分套 W Q S WQS WQS二分。


D P DP DP转移

W Q S WQS WQS二分后,就是 D P DP DP了。

我们可以用 f i f_i fi表示到第 i i i个神奇宝贝为止捕捉到的神奇宝贝总数的最大期望值,并用 g 1 i g1_i g1i表示此时使用的第一种捕捉球个数,用 g 2 i g2_i g2i表示此时使用的第二种捕捉球个数

其实 D P DP DP也是挺简单的,共有 4 4 4种情况:

  • 不使用捕捉球。 f i = f i − 1 , g 1 i = g 1 i − 1 , g 2 i = g 2 i − 1 f_i=f_{i-1},g1_i=g1_{i-1},g2_i=g2_{i-1} fi=fi1,g1i=g1i1,g2i=g2i1
  • 使用第一种捕捉球。 f i = f i − 1 + s 1 i − C 1 , g 1 i = g 1 i − 1 + 1 , g 2 i = g 2 i − 1 f_i=f_{i-1}+s1_i-C1,g1_i=g1_{i-1}+1,g2_i=g2_{i-1} fi=fi1+s1iC1,g1i=g1i1+1,g2i=g2i1
  • 使用第二种捕捉球。 f i = f i − 1 + s 2 i − C 2 , g 1 i = g 1 i − 1 , g 2 i = g 2 i − 1 + 1 f_i=f_{i-1}+s2_i-C2,g1_i=g1_{i-1},g2_i=g2_{i-1}+1 fi=fi1+s2iC2,g1i=g1i1,g2i=g2i1+1
  • 同时使用两种捕捉球。 f i = f i − 1 + s 1 i + s 2 i − C 1 − C 2 − s 1 i ∗ s 2 i , g 1 i = g 1 i − 1 + 1 , g 2 i = g 2 i − 1 + 1 f_i=f_{i-1}+s1_i+s2_i-C1-C2-s1_i*s2_i,g1_i=g1_{i-1}+1,g2_i=g2_{i-1}+1 fi=fi1+s1i+s2iC1C2s1is2i,g1i=g1i1+1,g2i=g2i1+1

这样就可以了。


代码

#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define N 100000
#define eps 1e-12
using namespace std;
int n,A,B;double s1[N+5],s2[N+5];
class Class_WQS//WQS二分套WQS二分
{
    private:
        double C1,C2,f[N+5];int g1[N+5],g2[N+5];//用f[i]表示到第i个神奇宝贝为止捕捉到的神奇宝贝总数的最大期望值,并用g1[i]表示此时使用的第一种捕捉球个数,用g2[i]表示此时使用的第二种捕捉球个数
        inline void check()//DP转移
        {
            for(register int i=1;i<=n;++i)
            {
                f[i]=f[i-1],g1[i]=g1[i-1],g2[i]=g2[i-1];//不使用捕捉球
                if(f[i-1]+(s1[i]-C1)-f[i]>eps) f[i]=f[i-1]+(s1[i]-C1),g1[i]=g1[i-1]+1,g2[i]=g2[i-1];//使用第一种捕捉球
                if(f[i-1]+(s2[i]-C2)-f[i]>eps) f[i]=f[i-1]+(s2[i]-C2),g1[i]=g1[i-1],g2[i]=g2[i-1]+1;//使用第二种捕捉球
                if(f[i-1]+(s1[i]+s2[i]-C1-C2-s1[i]*s2[i])-f[i]>eps) f[i]=f[i-1]+(s1[i]+s2[i]-C1-C2-s1[i]*s2[i]),g1[i]=g1[i-1]+1,g2[i]=g2[i-1]+1;//同时使用两种捕捉球
 			}
 		}
 		inline void GetRes()//第二层二分,二分C2
 		{
            register double l=0.0,r=1.0;
            for(C2=(l+r)/2;r-l>eps;C2=(l+r)/2) 
            {
                if(check(),!(g2[n]^B)) return;//找到符合条件的C2,就可以return了
                g2[n]>B?l=C2:r=C2;//如果选得物品数量偏多,将l更新为C2,否则将r更新为C2
            }
        }
    public:
        inline double GetAns()//第一层二分,二分C1
        {
            register double l=0.0,r=1.0;
            for(C1=(l+r)/2;r-l>eps;C1=(l+r)/2) 
            {
                if(GetRes(),!(g1[n]^A)) break;//找到符合条件的C1,就可以break了
                g1[n]>A?l=C1:r=C1;//如果选得物品数量偏多,将l更新为C1,否则将r更新为C1
            }
            return f[n]+A*C1+B*C2;//返回答案
        }
}WQS;
int main()
{
    register int i;
	scanf("%d%d%d",&n,&A,&B);
    for(i=1;i<=n;++i) scanf("%lf",&s1[i]);
    for(i=1;i<=n;++i) scanf("%lf",&s2[i]);
    return printf("%.10lf\n",WQS.GetAns()),0;
}
 类似资料: