首页 > 代码库 > BZOJ 3963: [WF2011]MachineWorks [CDQ分治 斜率优化DP]
BZOJ 3963: [WF2011]MachineWorks [CDQ分治 斜率优化DP]
传送门
当然了WF的题uva hdu上也有
你的公司获得了一个厂房N天的使用权和一笔启动资金，你打算在这N天里租借机器进行生产来获得收益。
可以租借的机器有M台。每台机器有四个参数D,P,R,G。你可以在第D天花费P的费用（当然，前提是你有至少P元）租借这台机器，从第D+1天起，操作机器将为你产生每天G的收益。在你不再需要机器时，可以将机器卖掉，一次性获得R的收益。
厂房里只能停留一台机器。
不能在购买和卖出机器的那天操作机器，但是可以在同一天卖掉一台机器再买入一台。
在第N+1天，你必须卖掉手上的机器。
求第N+1天后能获得的最大资金。
$DP-naive$相当好写
$f[i]$为第$i$天卖掉后最大收益
$f[i]=max{f[i-1],f[j]-P_j+R_j+G_j*(D_i-D_j-1)}$
然后变成点斜式
$f_i=A_j+G_j*D_i$
$A_j=-D_i*G_j+f_i$
$(G_j,A_j)$是点，斜率$D_i$正好按时间排序后单调(也就是说本题时间和斜率是一个东西，不用像$cash$那样按斜率排序然后分治里要先按时间分成两块)
然后$CDQ$分治维护上凸壳就行啦
从fuxey那里学到可以用计算几何那一套来避免精度问题，太棒啦！
然后我花了两节课调试修改，主要是因为：
本题的$y$需要加上$f$啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
我一开始不考虑$f$结果狂$WA$，然后发现$fuxey$求凸包额外排序了才想到应该加上$f$
但是复杂度加一个$log$好别扭啊
于是我把$f$放到归并的比较里，又狂$WA$
然后发现$f$的下标需要用按时间排序后的下标，又去保存了一个$id$........
还有一点，要保证$f[j]>P_j$才能买
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=1e5+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}struct Vector{ ll x,y; Vector(ll a=0,ll b=0):x(a),y(b){}};Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}typedef Vector Point;double Cross(Vector a,Vector b){return (double)a.x*b.y-(double)a.y*b.x;}int n,D;struct Machine{ int d,p,r,g; ll x,y; int id; void ini(){ d=read();p=read();r=read();g=read(); x=g;y=-p+r-(ll)d*g-g; }}a[N],t[N];inline bool cmpDay(const Machine &a,const Machine &b){return a.d<b.d;}ll f[N];inline bool cmp(int i,int j){return a[i].x==a[j].x ? a[i].y+f[a[i].id]<a[j].y+f[a[j].id] : a[i].x<a[j].x;}Point p[N],ch[N];inline ll line(ll k,Point &p){return k*p.x+p.y;}void CDQ(int l,int r){ if(l==r){f[l]=max(f[l],f[l-1]);return;} int mid=(l+r)>>1; CDQ(l,mid); int n=0,m=0; for(int i=l;i<=mid;i++) if(f[a[i].id]>=a[i].p) //!!!!! p[++n]=Point(a[i].x,a[i].y+f[a[i].id]); for(int i=1;i<=n;i++){ while(m>1&&Cross(ch[m]-ch[m-1],p[i]-ch[m-1])>=0) m--; ch[++m]=p[i]; } int j=1; for(int i=mid+1;i<=r;i++){ while(j<m&&line(a[i].d,ch[j+1])>=line(a[i].d,ch[j])) j++; if(j<=m) f[i]=max(f[i],line(a[i].d,ch[j])); } CDQ(mid+1,r); int p1=l,p2=mid+1; for(int i=l;i<=r;i++){ if(p2>r||(p1<=mid&&cmp(p1,p2))) t[i]=a[p1++]; else t[i]=a[p2++]; } for(int i=l;i<=r;i++) a[i]=t[i];}int main(){ freopen("in","r",stdin); int cas=0; while(scanf("%d%lld%d",&n,&f[0],&D)!=EOF){ if(n==0&&f[0]==0&&D==0) break; for(int i=1;i<=n;i++) a[i].ini(); a[++n].d=D+1; sort(a+1,a+1+n,cmpDay); for(int i=1;i<=n;i++) a[i].id=i,f[i]=0; CDQ(1,n); printf("Case %d: %lld\n",++cas,f[n]); }}
BZOJ 3963: [WF2011]MachineWorks [CDQ分治 斜率优化DP]