about 4 years ago

其实动态凸包是应该用平衡树维护的

但是……没有写出来而且难写

所以上cdq分治

基本思想就是取中点,左右分开解决,因为左边已完成,故左边都可以影响右边,可用单调栈

不知道为什么在向外弹栈的时候要用结果最大值作为条件……而不是斜率……或许是我写渣了。

注意!:

对凸包斜率递增递减,查询斜率递增递减,维护上凸壳还是下凸壳,用单调栈还是单调队列,都要有明确且清晰的判断

详细的题解

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define maxn 100001
#define eps 1e-7
using namespace std;
int pos[maxn]={0};
double money[maxn]={0.0},k[maxn]={0.0},a[maxn]={0.0},b[maxn]={0.0},rate[maxn]={0.0};
int n;
double answer=0.0;
struct point
{
double x,y;
} f[maxn],temp[maxn];
int stack[maxn]={0};
double max(double x,double y)
{
if (x>y) return x;else return y;
}
double fabs(double x)
{
if (x<0) return -x;else return x;
}
int dcmp(double x,double y)
{
if (fabs(x-y)<eps) return 0;
if (x>y) return 1;else return -1;
}
bool change(int x)
{
if (x==-1) return true;else return false;
}
bool operator <(point a,point b)
{
if (dcmp(a.x,b.x)==0) return change(dcmp(a.y,b.y));
return change(dcmp(a.x,b.x));
}
bool cmp_pos(int x,int y)
{
return k[x]<k[y];
}
double xl(int x,int y)
{
return (f[y].y-f[x].y)/(f[y].x-f[x].x);
}
long double sell(point thePoint, int day)
{
return thePoint.x * a[day] + thePoint.y * b[day];
}
void solve(int left,int right)
{
if (left==right)
{
answer=max(answer,money[left]);
f[left].x=answer/(a[left]+b[left]/rate[left]);
f[left].y=f[left].x/rate[left];
return;
}
int i,j,mid=(left+right)>>1,l1=left,l2=mid+1;
memmove(stack+left,pos+left,sizeof(int)*(right-left+1));
for (i=left;i<=right;i++)
if (stack[i]<=mid) pos[l1++]=stack[i];else pos[l2++]=stack[i];
solve(left,mid);int top=0;
if (mid+1==8)
{
int o;
o++;
}
for (i=left;i<=mid;i++)
{
while (top>1&&dcmp(xl(stack[top-1],stack[top]),xl(stack[top],i))<=0) top--;
stack[++top]=i;
}
for (i=mid+1;i<=right;i++)
{
while (top>1&&sell(f[stack[top-1]], pos[i])>sell(f[stack[top]], pos[i])) top--;
money[pos[i]]=max(money[pos[i]],sell(f[stack[top]], pos[i]));
}
solve(mid+1,right);
merge(f+left,f+mid+1,f+mid+1,f+right+1,temp+left);
memmove(f+left,temp+left,sizeof(point)*(right-left+1));
}
int main()
{
int i,j,l,s,t;
scanf("%d%lf",&n,&money[1]);
for (i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
k[i]=-a[i]/b[i];pos[i]=i;
}
sort(pos+1,pos+n+1,cmp_pos);
solve(1,n);
printf("%.3lf\n",answer);
}
← 【bzoj2668】【费用流】交换棋子 【bzoj2539】【KM】丘比特的烦恼 →
 
comments powered by Disqus