[latexpage]
Description
你是任意性复杂机器公司(Arbitrarily Complex Machines, ACM)的经理，公司使用更加先进的机械设备生产先进的机器。原来的那一台生产机器已经坏了，所以你要去为公司买一台新的生产机器。你的任务是在转型期内尽可能得到更大的收益。在这段时间内，你要买卖机器，并且当机器被ACM公司拥有的时候，操控这些机器以获取利润。因为空间的限制，ACM公司在任何时候都只能最多拥有一台机器。
在转型期内，有若干台可能卖出的机器。作为先进机器的专家，对于每台机器Mi，你已经知道了其价格Pi和可以买入的日期Di。注意，如果不在第Di天买入机器Mi，那么别的人也会买走这一台机器，也就是说，以后你将没有机会购买这台机器了。如果ACM的钱低于一台机器的价格，那么你显然不可能买到这一台机器。
如果你在第Di天买入了机器Mi,那么ACM公司可以从第(Di)+1天开始使用这一台机器。每使用这台机器一天，就可以为公司创造出Gi美元的收益。
你可以决定要在买入之后的某一天，以一定的折扣价卖出这一台机器。收购市场对于每一台机器，都有一个折扣价Ri。你不能在卖出的那一天使用机器，但是你可以在卖出的那一天再买入一台新的。
在转型期结束后，ACM公司会卖掉当前所拥有的机器。你的任务就是最大化转型期间ACM公司可以得到的收入。
Input
输入包含若干组测试用例。每一组测试用例的第一行有3个正整数N，C和D。N是将会卖出的机器的台数(N<=10^5)，C是在转型期开始时公司拥有的美元数量(C<=10^9)，D是转型期持续的天数(D<=10^9)。
之后的N行每一行描述了一台机器的情况。每一行有4个正整数Di,Pi,Ri和Gi,分别表示这台机器卖出的时间，购买这台机器需要的美元数量，卖出这台机器的折扣价和使用这台机器可以得到的利润。这些数字满足1<=Di<=D,1<=Ri<Pi<=10^9且1<=Gi<=10^9.
最后一组测试用例后面的一行由3个0组成，表示输入数据。
Output
对于每一组测试用例，输出测试用例的编号，之后给出ACM公司在第D+1天结束后可以得到的最大数量的美元。
请依照下面给出的样例输出。
Sample Input
6 10 20
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 0 0
6 12 1 3
1 9 1 2
3 2 1 2
8 20 5 4
4 11 7 4
2 10 9 1
0 0 0
Sample Output
Case 1: 44
Solution
先按时间排序。
令$f[i]$为第$i$个机器刚购买完所剩的最多金钱数。
则$f[i]=max{ f[j]+(Di-Dj-1)*Gj+Rj-Pi } $
若$f[i]<0$那么就说明不能买第$i$个机器了。
然后我们发现这个式子似乎可以用斜率优化来优化，
即令$j<k<i$，
当$j$比$k$差时 $f[j]+(Di-Dj-1)*Gj+Rj-Pi<f[k]+(Di-Dk-1)*Gk+Rk-Pi $
$f[j]-f[k]+(Dk+1)*Gk-(Dj+1)*Gj+Rj-Rk<Di*(Gk-Gj)$
但我们发现$Gk$与$Gj$的关系是不定的，那我们就不能确定不等号的方向了。
这时，我们可以用CDQ分治来解决这个问题，对于$[L,R]$的区间，用$[L,mid]$来更新$[mid+1,R]$，
那么只要把$[L,mid]$按$Gi$排序,$[mid+1,R]$按$Ti$排序即可。
对于$Ti$排序可以在分治之前先排序，对于$Gi$排序只要归并就好了，这样时间复杂度就是Θ(NlgN)的了。
在下面给出的代码中，$g[i]$即为$f[i]$，$Wi$即为$Gi$。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long using namespace std; const int N=100100; int n,q[N]; ll S,T,g[N]; struct node{ll d,c,r,w,g;}a[N],b[N]; bool cmp(node a,node b) { return a.d<b.d;} long double Calc(int j,int k) { long double X=(long double)((a[j].d+1)*a[j].w-(a[k].d+1)*a[k].w-a[j].g-a[j].r+a[k].g+a[k].r); if (a[j].w==a[k].w) return (X<0)?1LL<<60:-(1LL<<60); return X/(long double)(a[j].w-a[k].w); } void CDQ(int l,int r) { if (l==r) return; int mid=(l+r)/2; CDQ(l,mid); int top=0; for (int i=l;i<=mid;i++) if (a[i].g>=0) { while (top>1&&Calc(q[top-1],q[top])>=Calc(q[top],i)) top--; q[++top]=i; } int head=1; for (int i=mid+1;i<=r;i++) { while (head<top&&Calc(q[head],q[head+1])<=a[i].d) head++; ll sum=(a[i].d-a[q[head]].d-1)*a[q[head]].w+a[q[head]].g+a[q[head]].r; if (sum>=a[i].c) a[i].g=max(a[i].g,sum-a[i].c); } CDQ(mid+1,r); int i=l,j=mid+1,cnt=0; while (i<=mid&&j<=r) { if (a[i].w<a[j].w) b[++cnt]=a[i++]; else b[++cnt]=a[j++]; } for (;i<=mid;i++) b[++cnt]=a[i]; for (;j<=r;j++) b[++cnt]=a[j]; for (int k=l;k<=r;k++) a[k]=b[k-l+1]; } int main() { int CaseT=0; while (true) { scanf("%d%lld%lld",&n,&S,&T); if (n==0&&S==0&&T==0) break; for (int i=1;i<=n;i++) { scanf("%lld%lld%lld%lld",&a[i].d,&a[i].c,&a[i].r,&a[i].w); a[i].g=-1LL<<60; } a[++n]=(node){0,0,0,0,S}; sort(a+1,a+n+1,cmp); CDQ(1,n); ll ans=0; for (int i=1;i<=n;i++) if (a[i].g>=0) ans=max(ans,a[i].g+(T-a[i].d)*a[i].w+a[i].r); printf("Case %d: %lld\n",++CaseT,ans); } return 0; } |
%%%
%%%
%%%
