1 条题解
-
0
#include<bits/stdc++.h> using namespace std; #define db double #define eps 1e-9//一定要注意精度 #define inf 1e9 const int N=100005; int n,rt,sc,f[N],son[N][2]; db dp[N],A[N],B[N],R[N],lk[N],rk[N],X[N],Y[N];//lk:凸包点x左线斜率,rk:右线斜率 int is(int x) {return son[f[x]][1]==x;} void spin(int x,int &mb) { int fa=f[x],g=f[fa],t=is(x); if(fa==mb) mb=x; else son[g][is(fa)]=x; f[fa]=x,f[x]=g,f[son[x][t^1]]=fa; son[fa][t]=son[x][t^1],son[x][t^1]=fa; } void splay(int x,int &mb) { while(x!=mb) { if(f[x]!=mb) { if(is(x)^is(f[x])) spin(x,mb); else spin(f[x],mb); } spin(x,mb); } } int find(int x,db num) {//寻找最优解 if(!x) return 0; if(lk[x]+eps>=num&&rk[x]<=num+eps) return x; else if(lk[x]<num+eps) return find(son[x][0],num); else return find(son[x][1],num); } db getk(int a,int b) {//获得斜率 if(X[a]-X[b]<eps&&X[a]-X[b]>-eps) return -inf; return (Y[b]-Y[a])/(X[b]-X[a]); } int pre(int x) {//寻找左边最后一个与x可以构成凸包的点 int y=son[x][0],re=y; while(y) { if(lk[y]+eps>=getk(y,x)) re=y,y=son[y][1]; else y=son[y][0]; } return re; } int nxt(int x) {//寻找右边第一个与x可以构成凸包的点 int y=son[x][1],re=y; while(y) { if(rk[y]<=getk(x,y)+eps) re=y,y=son[y][0]; else y=son[y][1]; } return re; } void newjd(int x) { splay(x,rt); if(son[x][0]) { int kl=pre(x); splay(kl,son[x][0]),son[kl][1]=0; lk[x]=rk[kl]=getk(kl,x); } else lk[x]=inf;//请勿往左 if(son[x][1]) { int kl=nxt(x); splay(kl,son[x][1]),son[kl][0]=0; rk[x]=lk[kl]=getk(x,kl); } else rk[x]=-inf;//请勿往右 if(lk[x]<=rk[x]+eps) {//在原凸包内部,直接删除该点 rt=son[x][0],son[rt][1]=son[x][1],f[son[x][1]]=rt,f[rt]=0; lk[rt]=rk[son[rt][1]]=getk(rt,son[rt][1]); } } void ins(int &x,int las,int bh) { if(!x) {x=bh,f[x]=las;return;} if(X[bh]<=X[x]+eps) ins(son[x][0],x,bh); else ins(son[x][1],x,bh); } int main() { scanf("%d%lf",&n,&dp[0]); for(int i=1;i<=n;++i) { scanf("%lf%lf%lf",&A[i],&B[i],&R[i]); int j=find(rt,-A[i]/B[i]); dp[i]=max(dp[i-1],X[j]*A[i]+Y[j]*B[i]); Y[i]=dp[i]/(A[i]*R[i]+B[i]),X[i]=Y[i]*R[i]; ins(rt,0,i),newjd(i); } printf("%.3lf\n",dp[n]); return 0; }
- 1
信息
- ID
- 1492
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 27
- 已通过
- 13
- 上传者