首页 > 代码库 > BZOJ1492: [NOI2007]货币兑换Cash
BZOJ1492: [NOI2007]货币兑换Cash
CDQ的论文讲的非常清楚了
事实上这一道题写成斜率优化的形式之后我们会发现一个非常严重的问题 斜率不是单调的
然后能用斜率优化么?能够。
。
。用CDQ将前一半的决策点处理一边 后一半就能线性更新了
然后总的复杂度是CDQ分治的复杂度
%%%CDQ
代码的话是直接copy的 昨天打代码手打残了 不想打了
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define eps 1e-9 #define inf 0x7fffffff #define ll long long using namespace std; int n,top,stack[200005]; double f[200005]; struct point{double x,y,a,b,k,rate;int id,w;}p[100005],t[100005]; 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); } inline bool operator<(point a,point b){return a.k>b.k;} void solve(int l,int r) { if(l==r) { f[l]=max(f[l],f[l-1]); 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 l1,l2,mid=(l+r)>>1,j=1; l1=l;l2=mid+1; 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); top=0; for(int i=l;i<=mid;i++) { while(top>1&&getk(stack[top-1],stack[top])<getk(stack[top-1],i)+eps) top--; stack[++top]=i; } stack[++top]=0; for(int i=mid+1;i<=r;i++) { while(j<top&&getk(stack[j],stack[j+1])+eps>p[i].k)j++; f[p[i].id]=max(f[p[i].id],p[stack[j]].x*p[i].a+p[stack[j]].y*p[i].b); } solve(mid+1,r); l1=l;l2=mid+1; 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)t[i]=p[l1++]; else t[i]=p[l2++]; for(int i=l;i<=r;i++)p[i]=t[i]; } 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].rate); p[i].k=-p[i].a/p[i].b;p[i].id=i; } sort(p+1,p+n+1); solve(1,n); printf("%.3lf",f[n]); return 0; }
BZOJ1492: [NOI2007]货币兑换Cash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。