【Codeforces】739E. Gosha is hunting【WQS二分】

E. Gosha is hunting

【题目描述】

传送门

【题解】

这题官方题解不是WQS二分。 首先最优解肯定是f[n][a][b]。 将DP消去一维，没有b的限制，那么肯定每个只猫都会选择B[i]，所以我们就二分一个值，限制选择的个数。 当然还可以更优，WQS二分套WQS二分，既然B[i]可以二分，那么A[i]也可以。

代码如下 $O(n^{2}logn)$

#include<cstdio> #include<cstring> #include<iostream> #define EXP 1e-6 using namespace std; int n,a,b;double Ans,A[2005],B[2005],f[2][2005],g[2][2005]; void UPD(double &x,double y){if(x<y) x=y;} bool Solve(double Dec){ memset(f,0,sizeof(f));memset(g,0,sizeof(g));int l=0,r=1; for(int i=1;i<=n;i++,l^=1,r^=1){ for(int j=0;j<=a&&j<=i;j++){ f[r][j]=f[l][j],g[r][j]=g[l][j]; if(f[r][j]<f[l][j]+B[i]-Dec) f[r][j]=f[l][j]+B[i]-Dec,g[r][j]=g[l][j]+1; if(j&&f[r][j]<f[l][j-1]+A[i]) f[r][j]=f[l][j-1]+A[i],g[r][j]=g[l][j-1]; if(j&&f[r][j]<f[l][j-1]+A[i]+B[i]-Dec-A[i]*B[i]) f[r][j]=f[l][j-1]+A[i]+B[i]-Dec-A[i]*B[i],g[r][j]=g[l][j-1]+1; } } f[l][a]+=Dec*b;return g[l][a]<=b; } int main(){ while(~scanf("%d%d%d",&n,&a,&b)){ for(int i=1;i<=n;i++) scanf("%lf",A+i); for(int i=1;i<=n;i++) scanf("%lf",B+i); for(double L=-1,R=3,mid=(R+L)/2;R-L>=EXP;mid=(R+L)/2) if(Solve(mid)) Ans=R=mid;else L=mid; Solve(Ans); printf("%.6lf\n",f[n&1][a]); } return 0; }

最优方法$O(nlo{g}^{2}n)$

#include<cstdio> #include<cstring> #include<iostream> #define EXP 1e-6 using namespace std; int n,a,b,g[2],G[2];double Ans,A[2005],B[2005],f[2]; bool Solve(double Dec1,double Dec2){ memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(G,0,sizeof(G)); for(int i=1,l=0,r=1;i<=n;i++,l^=1,r^=1){ f[r]=f[l],g[r]=g[l],G[r]=G[l]; if(f[r]<f[l]+A[i]-Dec1) f[r]=f[l]+A[i]-Dec1,g[r]=g[l] ,G[r]=G[l]+1; if(f[r]<f[l]+B[i]-Dec2) f[r]=f[l]+B[i]-Dec2,g[r]=g[l]+1,G[r]=G[l] ; if(f[r]<f[l]+A[i]+B[i]-Dec1-Dec2-A[i]*B[i]) f[r]=f[l]+A[i]+B[i]-Dec1-Dec2-A[i]*B[i],g[r]=g[l]+1,G[r]=G[l]+1; } return G[n&1]<=a; } bool check(double Dec){ double Now=0; for(double L=-1,R=3,mid=(R+L)/2;R-L>=EXP;mid=(R+L)/2) if(Solve(mid,Dec)) Now=R=mid;else L=mid; Solve(Now,Dec);f[n&1]+=Now*a; return g[n&1]<=b; } int main(){ while(~scanf("%d%d%d",&n,&a,&b)){ for(int i=1;i<=n;i++) scanf("%lf",A+i); for(int i=1;i<=n;i++) scanf("%lf",B+i); for(double L=-1,R=3,mid=(R+L)/2;R-L>=EXP;mid=(R+L)/2) if(check(mid)) Ans=R=mid;else L=mid; check(Ans);f[n&1]+=Ans*b; printf("%.6lf\n",f[n&1]); } return 0; }