CF739E Gosha is hunting-白红宇

CF739E Gosha is hunting

阅读量：4501 次

发布时间：2019-06-08

本文共 1154 字，大约阅读时间需要 3 分钟。

暴力\(N^3\)dp就是\(f_{i,j,k}\),前\(i\)个东西,用\(j\)个第一个球和\(k\)个第二个球

然后可以发现随着限制\(a\)以及\(b\)的增加,答案是一个上凸函数,所以可以二分(好像叫\(wqs\)二分).二分第一维以及第二维的代价,然后做没有个数限制的dp,转移记录两种球用了多少个,以及转移时要每用一个球答案减去对应的代价.根据用到球个数调整二分边界,直到用的球个数都等于限制\(a\)和\(b\)就能求出答案

~~然后二分边界被卡的飞起qwq~~

//WA代码#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define LL long long#define db doubleusing namespace std;const int N=2000+10;const db eps=1e-6;LL rd(){ LL x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return x*w;}int n;db aa,bb,a[N],b[N],c[N],f[N],na[N],nb[N];void cal(db m1,db m2){ for(int i=1;i<=n;++i) { f[i]=f[i-1],na[i]=na[i-1],nb[i]=nb[i-1]; if(f[i]
               
                eps) { db m1=(l1+r1)/2; db l2=0,r2=1; while(r2-l2>eps) { db m2=(l2+r2)/2; cal(m1,m2); if(nb[n]<=bb) z2=m2,r2=m2-eps; else l2=m2+eps; } cal(m1,z2); if(na[n]<=aa) z1=m1,r1=m1-eps; else l1=m1+eps; } cal(z1,z2); printf("%.5lf\n",f[n]+na[n]*z1+nb[n]*z2); return 0;}

转载于:https://www.cnblogs.com/smyjr/p/11012799.html

你可能感兴趣的文章