BZOJ3963: [WF2011]MachineWorks[dp]

Description

你是任意性复杂机器公司(Arbitrarily Complex Machines, ACM)的经理,公司使用更加先进的机械设备生产先进的机器。原来的那一台生产机器已经坏了,所以你要去为公司买一台新的生产机器。你的任务是在转型期内尽可能得到更大的收益。在这段时间内,你要买卖机器,并且当机器被ACM公司拥有的时候,操控这些机器以获取利润。因为空间的限制,ACM公司在任何时候都只能最多拥有一台机器。

在转型期内,有若干台可能卖出的机器。作为先进机器的专家,对于每台机器Mi,你已经知道了其价格$P_i$ 和可以买入的日期 $D_i$。注意,如果不在第 $D_i$ 天买入机器Mi,那么别的人也会买走这一台机器,也就是说,以后你将没有机会购买这台机器了。如果ACM的钱低于一台机器的价格,那么你显然不可能买到这一台机器。

如果你在第 $D_i$ 天买入了机器Mi,那么ACM公司可以从第$(D_i)+1$天开始使用这一台机器。每使用这台机器一天,就可以为公司创造出$G_i$美元的收益。

你可以决定要在买入之后的某一天,以一定的折扣价卖出这一台机器。收购市场对于每一台机器,都有一个折扣价 $R_i$ 。你不能在卖出的那一天使用机器,但是你可以在卖出的那一天再买入一台新的。

在转型期结束后,ACM公司会卖掉当前所拥有的机器。你的任务就是最大化转型期间ACM公司可以得到的收入。

Input

输入包含若干组测试用例。每一组测试用例的第一行有3个正整数$N,C$和$D$。$N$是将会卖出的机器的台数$(N\le10^5)$,C是在转型期开始时公司拥有的美元数量 $(C\le10^9)$,D是转型期持续的天数$(D \le 10^9)$。

之后的N行每一行描述了一台机器的情况。每一行有4个正整数Di,Pi,Ri和Gi,分别表示这台机器卖出的时间,购买这台机器需要的美元数量,卖出这台机器的折扣价和使用这台机器可以得到的利润。这些数字满足 $1\le D_i\le D$,$1 \le R_i<P_i \le 10^9$且$1\le Gi\le10^9$.

最后一组测试用例后面的一行由3个0组成,表示输入数据。

Output

对于每一组测试用例,输出测试用例的编号,之后给出ACM公司在第 $D+1$$天结束后可以得到的最大数量的美元。

请依照下面给出的样例输出。

Sample Input

1
2
3
4
5
6
7
8
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

Sample Output

1
Case 1: 44

Solution

推一波暴力dp式子 $dp_i=max ( dp_j+ (D_i-D_j-1)*G_j+R_j-P_i )$

然后很简单嘛,斜率优化就可以过了

(谁告诉你$G_i$有单调性的)

于是可以用到cdq分治,对于一个区间 $x-y$ 先处理 $x-mid$ 再将 $x-mid$ 的dp值转移到 $mid+1-y$ 中,然后 $x-y$按 $g_i$ 从小到大排序。然后就可以了。

写这道题的时候自己打错了一个变量名,改了好久,然后多组数据,有个地方自己没清空。

hk的博客写得更详细。

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
71
72
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll qmax(ll &x,ll y) {if (x<y) x=y;}
ll qmin(ll &x,ll y) {if (x>y) x=y;}
int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=1e5+10;
int n,c,d;
struct node
{
long long d,p,r,g,dp;//day d $p $r g
} a[100100];
node b[100100];
int q[100100],l,r,T;
long long ans;
bool cmp(node aa,node bb){return aa.d<bb.d;}
long double K(int x,int y)
{
long long s=-(a[x].d+1)*a[x].g+a[x].dp+a[x].r;
s-=-(a[y].d+1)*a[y].g+a[y].dp+a[y].r;
if (a[y].g-a[x].g==0) if (s<0) return -1e18; else return 1e18;
return (long double)s/(long double)(a[y].g-a[x].g);
}
void ef(int x,int y)
{
if (x==y) return;int mid=(x+y)>>1;ef(x,mid);l=1;r=0;
for (int i=x;i<=mid;i++)
{
if (a[i].dp>=0) {while (l<r&&K(q[r-l],q[r])>=K(q[r],i)) r--;q[++r]=i;}
}
for (int i=mid+1;i<=y;i++)
{
while (l<r&&a[i].d>=K(q[l],q[l+1])) l++;int j=q[l];
a[i].dp=max(a[i].dp,(a[j].dp+(a[i].d-a[j].d-1)*a[j].g+a[j].r-a[i].p)>=0 ? (a[j].dp+(a[i].d-a[j].d-1)*a[j].g+a[j].r-a[i].p):(long long)-1e18);
}
ef(mid+1,y);
int i=x,j=mid+1;int p=x-1;
while (i<=mid&&j<=y) if (a[i].g<a[j].g) b[++p]=a[i++]; else b[++p]=a[j++];
while (i<=mid) b[++p]=a[i++];while (j<=y) b[++p]=a[j++];
for (i=x;i<=y;i++) a[i]=b[i];
}
int main()
{
while (true)
{
n=read();c=read();d=read();if (!n&&!c&&!d) return 0;
for (int i=1;i<=n;i++)
{
a[i].dp=-1e18;
a[i].d=read();a[i].p=read();a[i].r=read();a[i].g=read();
}
ans=0;
a[++n].dp=c;a[n].d=a[n].p=a[n].r=a[n].g=0;
sort(a+1,a+n+1,cmp);
ef(1,n);
for (int i=1;i<=n;i++) if (a[i].dp>=0) ans=max(ans,a[i].dp+a[i].r+a[i].g*(d-a[i].d));
printf("Case %d: %lld\n",++T,ans);
}
return 0;
}