hdu 3842 Machine Works(cdq分治维护凸壳)

细节比较多，好好体会一下。
在维护斜率的时候要考虑x1与x2是否相等，这里要处理一下。
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;i++)
 3 using namespace std;
 4 typedef long long ll;
 5 typedef pair<int,ll>P;
 6 
 7 const int N=1e5+7;
 8 int n,c,d,cas;
 9 ll dp[N];
10 struct node{
11     int D,P,R,G;
12     bool operator < (const node &b)const{return D<b.D;}
13 }a[N];
14 P A[N],Q[N];
15 
16 ll h(int j){return dp[j]-a[j].P-(ll)(a[j].D+1)*a[j].G+a[j].R;}
17 inline void up(ll &a,ll b){if(a<b)a=b;}
18 
19 int check(P a,P b,P c)
20 {
21     ll y1=b.second-a.second,y2=c.second-b.second;
22     ll x1=b.first-a.first,x2=c.first-b.first;
23     return (double)x1*y2>=(double)x2*y1;
24 }
25 
26 void cdq(int l=0,int r=n)
27 {
28     if(l==r)return;
29     int mid=l+r>>1;
30     cdq(l,mid);
31     int head=1,tail=0,ed=0;
32     F(i,l,mid)if(dp[i]>=a[i].P)A[++ed]=P(a[i].G,h(i));
33     sort(A+1,A+1+ed);
34     F(i,1,ed)
35     {
36         while(head<tail&&check(Q[tail-1],Q[tail],A[i]))tail--;
37         Q[++tail]=A[i];    
38     }
39     F(i,mid+1,r)
40     {
41         while(head<tail&&Q[head+1].second-Q[head].second>=-(ll)a[i].D*(Q[head+1].first-Q[head].first))head++;
42         up(dp[i],(ll)Q[head].first*a[i].D+Q[head].second);
43     }
44     
45     cdq(mid+1,r);
46 }
47 
48 int main()
49 {
50     while(scanf("%d%d%d",&n,&c,&d),n+c+d)
51     {
52         F(i,1,n)scanf("%d%d%d%d",&a[i].D,&a[i].P,&a[i].R,&a[i].G);
53         sort(a+1,a+1+n);
54         a[++n].D=d+1,a[n].G=a[n].P=a[n].R=0;
55         F(i,0,n)dp[i]=c;
56         cdq();
57         printf("Case %d: %lld
",++cas,dp[n]);
58     }
59     return 0;
60 }
View Code