http://www.lydsy.com/JudgeOnline/problem.php?id=1492
思路:
问题转变为维护一个凸包，每次转移都找凸包上的点，并更新凸壳
可以用splay维护，或者说，可以用cdq分治去维护，左半边构成的凸壳对右半边答案的影响~
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
const double eps=1e-;
double f[];
struct node{
double a,b,rate,x,y,k;
int id;
}p[],tmp[];
int n,stack[];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
bool cmp(node a,node b){
return a.k>b.k;
}
double getk(int a,int b){
if (!b) return -1e20;
if (fabs(p[a].x-p[b].x)<eps) return 1e20;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
void cdq(int l,int r){
if (l==r){
f[l]=std::max(f[l],f[l-]);
p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b);
p[l].x=p[l].rate*p[l].y;
return;
}
int mid=(l+r)>>;
int l1=l-,l2=mid;
for (int i=l;i<=r;i++)
if (p[i].id<=mid)
tmp[++l1]=p[i];
else
tmp[++l2]=p[i];
for (int i=l;i<=r;i++)
p[i]=tmp[i];
cdq(l,mid);
int top=;
for (int i=l;i<=mid;i++){
while (top>&&getk(stack[top-],stack[top])<getk(stack[top-],i)+eps) top--;
stack[++top]=i;
}
stack[++top]=;int j=;
for (int i=mid+;i<=r;i++){
while (j<top&&getk(stack[j],stack[j+])+eps>p[i].k) j++;
f[p[i].id]=std::max(f[p[i].id],p[stack[j]].x*p[i].a+p[stack[j]].y*p[i].b);
}
cdq(mid+,r);
l1=l,l2=mid+;
for (int i=l;i<=r;i++){
if ((((p[l1].x<p[l2].x)||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y))||l2>r)&&l1<=mid) tmp[i]=p[l1++];
else tmp[i]=p[l2++];
}
for (int i=l;i<=r;i++)
p[i]=tmp[i];
}
int main(){
scanf("%d",&n);scanf("%lf",&f[]);
for (int i=;i<=n;i++){
scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
p[i].k=-p[i].a/p[i].b;
p[i].id=i;
}
std::sort(p+,p++n,cmp);
cdq(,n);
printf("%.3lf",f[n]);
}
Splay代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
const double eps=1e-;
int fa[],ch[][];
double lk[],rk[];
double x[],y[],f[],rate[],a[],b[];
int n,root;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void rotate(int x,int &rt){
int y=fa[x],z=fa[y],l,r;
if (ch[y][]==x) l=;else l=;r=l^;
if (y!=rt){
if (ch[z][]==y) ch[z][]=x;
else ch[z][]=x;
}else rt=x;
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
}
void splay(int x,int &rt){
while (x!=rt){
int y=fa[x],z=fa[y];
if (y!=rt){
if ((ch[y][]==x)^(ch[z][]==y)) rotate(x,rt);
else rotate(y,rt);
}
rotate(x,rt);
}
}
void insert(int &k,int Fa,int id){
if (!k){
k=id;
fa[k]=Fa;
return;
}
if (x[k]+eps>=x[id]) insert(ch[k][],k,id);
else insert(ch[k][],k,id);
}
double getk(int i,int j){
if (fabs(x[i]-x[j])<eps) return -1e9;
else return (y[i]-y[j])/(x[i]-x[j]);
}
int pre(int rt){
int k=ch[rt][];int tmp=k;
while (k){
if (lk[k]+eps>=getk(k,rt)) tmp=k,k=ch[k][];
else k=ch[k][];
}
return tmp;
}
int suc(int rt){
int k=ch[rt][];int tmp=k;
while (k){
if (rk[k]<=eps+getk(k,rt)) tmp=k,k=ch[k][];
else k=ch[k][];
}
return tmp;
}
void updata(int k){
splay(k,root);
if (ch[k][]){
int left=pre(root);
splay(left,ch[k][]);ch[left][]=;
lk[k]=rk[left]=getk(k,left);
}else lk[k]=1e9;
if (ch[k][]){
int right=suc(root);
splay(right,ch[k][]);ch[right][]=;
lk[right]=rk[k]=getk(k,right);
}else rk[k]=-1e9;
if (lk[k]<=rk[k]+eps){
root=ch[k][];
ch[root][]=ch[k][];
fa[ch[k][]]=root;
fa[root]=;
rk[root]=lk[ch[k][]]=getk(root,ch[k][]);
}
}
int find(int k,double slop){
if (!k) return ;
if (lk[k]+eps>=slop&&slop+eps>=rk[k]){
return k;
}
if (slop+eps>lk[k]) return find(ch[k][],slop);
else return find(ch[k][],slop);
}
int main(){
n=read();scanf("%lf",&f[]);
for (int i=;i<=n;i++){
scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
}
for (int i=;i<=n;i++){
int j=find(root,-a[i]/b[i]);
f[i]=std::max(f[i-],x[j]*a[i]+b[i]*y[j]);
y[i]=f[i]/(a[i]*rate[i]+b[i]);
x[i]=y[i]*rate[i];
insert(root,,i);
updata(i);
}
printf("%.3f\n",f[n]);
}