cdq分治论文
cdq分治的应用之一 用来做斜率与X都不单调的斜率优化。。
cdq分治的大致套路就是先按某一个值进行排序
按照序号顺序归并分为 <=mid 与 >mid 的两部分
递归解决左区间的子问题 将左区间对右区间的影响加上 再递归解决右区间
体现在这里就是 先按k(斜率)值排序
按序号顺序排序 递归解决[l,mid]
并在递归结束时按x递增的顺序将区间内的点排序
这样左区间的f值已经为最优并且x递增 右区间按k值递增
将左区间的点依次入栈并维护一个凸壳 更新右区间的f值
最后在递归解决右区间即可
#include <cstdio>#include <cstring>#include <algorithm>#include <cstring>#include <cmath>#define MAXN 100005#define N 100#define INF 1000000005#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;const double eps = 1e-8;/*f[i]=f[j]/(a[j]*rate[j]+b[j])*rate[j]*a[i]+f[j]/(a[j]*rate[j]+b[j])*b[i] x[j]=f[j]/(a[j]*rate[j]+b[j])*rate[j] y[j]=f[j]/(a[j]*rate[j]+b[j]) ->f[i]=x[j]*a[i]+y[j]*b[i] ->y[j]=f[i]/b[i]-x[j]*a[i]/b[i]*/int n,l1,l2,top,st[MAXN];double f[MAXN];struct point{ double a,b,r,x,y,k; int id;}p[MAXN],t[MAXN];double k(int i,int j){ if(p[i].x-p[j].x==0) return p[i].y-p[j].y>0?INF:-INF; return (p[i].y-p[j].y)/(p[i].x-p[j].x);}void solve(int l,int r){//--f[l]为最优 计算x[l] y[l] if(l==r) { f[l]=max(f[l],f[l-1]); p[l].x=f[l]/(p[l].a*p[l].r+p[l].b)*p[l].r; p[l].y=f[l]/(p[l].a*p[l].r+p[l].b); return; } int mid=(l+r)>>1,j=1,l1=l,l2=mid+1;//--将p按位置排序 for(int i=l;i<=r;i++) if(p[i].id<=mid) t[l1++]=p[i]; else t[l2++]=p[i]; for(int i=l;i<=r;i++) p[i]=t[i];//--递归计算左区间 solve(l,mid);//--将左区间入栈 维护凸壳(此时左区间已经按x排好序) top=0; for(int i=l;i<=mid;i++) { while(top>1&&k(i,st[top])>k(st[top],st[top-1])) top--; st[++top]=i; }//--用左区间的点更新右区间的f for(int i=mid+1;i<=r;i++) { //f[i]=x[j]*a[i]+y[j]*b[i] while(j<top&&k(st[j],st[j+1])>p[i].k) j++; int tmp=st[j]; f[p[i].id]=max(f[p[i].id],p[tmp].x*p[i].a+p[tmp].y*p[i].b); }//--递归计算右区间 solve(mid+1,r);//--将L-R按x排序 l1=l,l2=mid+1; for(int i=l;i<=r;i++) if((l2>r||p[l1].x<p[l2].x)&&l1<=mid) t[i]=p[l1++]; else t[i]=p[l2++]; for(int i=l;i<=r;i++) p[i]=t[i];}bool cmp(point a,point b){return a.k>b.k;}int main(){ scanf("%d%lf",&n,&f[0]); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].r); p[i].k=-p[i].a/p[i].b,p[i].id=i; } sort(p+1,p+1+n,cmp); solve(1,n); PRintf("%.3lf",f[n]); return 0;}把while写成if结果调了一上午 我好菜啊。。
新闻热点
疑难解答
