首页 > > 程序设计 > C/C++ >

bzoj3963 [ WF2011 ] --cdq分治

2018-06-17 23:20:24来源：未知阅读 ()

思路与1492相同。

注意点：

1、叉乘时用long long会爆，要用double

2、凸包中可能什么都没有，这时不能更新。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define N 100010
 7 #define ll long long
 8 #define Eps 1e-9
 9 struct Node{
10   int Id;
11   ll y,k,x,p,r,g,d;
12 }a[N],t[N];
13 int i,j,C,k,n,m,St[N],Top;
14 ll f[N];
15 inline bool Cmp(Node a,Node b){return a.d<b.d;}
16 inline ll _Max(ll x,ll y){return x>y?x:y;}
17 inline bool Slopcmp(int x,int y,int z){
18   double p1=(double)(a[y].y-a[x].y)*(a[z].x-a[x].x);
19   double p2=(double)(a[z].y-a[x].y)*(a[y].x-a[x].x);
20   return p1<p2+Eps;
21 }
22 inline void Solve(int l,int r){
23   if(l==r){
24     f[l]=_Max(f[l-1],f[l]);
25     a[l].x=a[l].g;
26     a[l].y=f[l]-a[l].p+a[l].r-(a[l].d+1)*a[l].g;
27     return;
28   }
29   int Mid=l+r>>1;
30   int l1=l,l2=Mid+1;
31   for(int i=l;i<=r;i++)if(a[i].Id<=Mid)t[l1++]=a[i];else t[l2++]=a[i];
32   for(int i=l;i<=r;i++)a[i]=t[i];
33   Solve(l,Mid);
34   Top=0;
35   for(int i=l;i<=Mid;i++)
36     if(a[i].p<=f[a[i].Id]){
37       while(Top>1&&Slopcmp(St[Top-1],St[Top],i))Top--;
38       St[++Top]=i;
39     }
40   int j=1;
41   for(int i=Mid+1;i<=r;i++){
42     while(j<Top){
43       double p1=(double)a[i].k*(a[St[j+1]].x-a[St[j]].x);
44       double p2=a[St[j+1]].y-a[St[j]].y;
45       if(p1<p2+Eps)j++;else break;
46     }
47     if(j<=Top)f[a[i].Id]=_Max(f[a[i].Id],a[St[j]].y-a[i].k*a[St[j]].x);
48   }
49   Solve(Mid+1,r);
50   l1=l;l2=Mid+1;
51   for(int i=l;i<=r;i++)
52     if(l1>Mid)t[i]=a[l2++];else
53       if(l2>r)t[i]=a[l1++];else
54     if(a[l1].x<a[l2].x||(a[l1].x==a[l2].x&&a[l1].y<a[l2].y))t[i]=a[l1++];else t[i]=a[l2++];
55   for(int i=l;i<=r;i++)a[i]=t[i];
56 }
57 int main()
58 {
59   while(1){
60     scanf("%d%lld%lld",&n,&f[0],&m);
61     if(n==0)break;
62     for(i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&a[i].d,&a[i].p,&a[i].r,&a[i].g),a[i].k=-a[i].d;
63     a[++n].d=m+1;a[n].g=a[n].p=0;a[n].r=0;a[n].k=-a[n].d;
64     sort(a+1,a+n+1,Cmp);
65     for(i=1;i<=n;i++)a[i].Id=i,f[i]=f[0];
66     Solve(1,n);
67     printf("Case %d: %lld\n",++C,f[n]);
68   }
69   return 0;
70 }