Codeforces 629D Babaei and Birthday Cakes DP+线段树

题目：http://codeforces.com/contest/629/problem/D

题意：有n个蛋糕要叠起来，能叠起来的条件是蛋糕的下标比前面的大并且体积也比前面的大，问能叠成的最大体积

思路：DP[i]表示拿到第i个蛋糕时最多能叠成的体积，转移就是这样DP[i]=max(DP[1...i])+V[i];如果直接做的话复杂度是n^2的，用线段树维护比它小的蛋糕的能叠的最大体积，事先离散化，

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 #define PI acos(-1.0)
 8 const int maxn=1e5+10;
 9 struct cake{
10     int r,h;
11     double V;
12     cake(){};
13     cake(int r_,int h_):r(r_),h(h_){V=PI*r*r*h;};
14 };
15 struct node{
16     int l,r;
17     double maxx;
18     int mid(){return (l+r)>>1;}
19 };
20 node tree[maxn<<2];
21 void pushup(int rt){
22     tree[rt].maxx=max(tree[rt<<1].maxx,tree[rt<<1|1].maxx);
23 }
24 void build(int l,int r,int rt){
25     tree[rt].l=l,tree[rt].r=r;
26     tree[rt].maxx=0;
27     if(l==r) return ;
28     int mid=tree[rt].mid();
29     build(l,mid,rt<<1);
30     build(mid+1,r,rt<<1|1);
31 }
32 void update(int index,double C,int L,int R,int rt){
33     if(L==index&&R==index){
34         tree[rt].maxx=max(tree[rt].maxx,C);
35         return ;
36     }
37     int mid=tree[rt].mid();
38     if(index<=mid) update(index,C,L,mid,rt<<1);
39     else update(index,C,mid+1,R,rt<<1|1);
40     pushup(rt);
41 }
42 double query(int l,int r,int L,int R,int rt){
43     if(L>=l&&R<=r) {
44         return tree[rt].maxx;
45     }
46     double maxx=-1.0;
47     int mid=tree[rt].mid();
48     if(l<=mid) maxx=max(maxx,query(l,r,L,mid,rt<<1));
49     if(r>mid) maxx=max(maxx,query(l,r,mid+1,R,rt<<1|1));
50     return maxx;
51 }
52 cake a[maxn];
53 double v[maxn];
54 int n;
55 void solve(){
56     sort(v+1,v+1+n);
57     int size=unique(v+1,v+1+n)-v;
58     double ans=0;
59     build(1,size,1);
60     double tmp;
61     for(int i=1;i<=n;i++){
62         int pos=lower_bound(v+1,v+size,a[i].V)-v;
63         tmp=0;
64         tmp=query(1,pos-1,1,size,1);
65         if(pos-1==0) tmp=0;
66         tmp+=a[i].V;
67         ans=max(ans,tmp);
68         update(pos,tmp,1,size,1);
69     }
70     printf("%.10f
",ans);
71 }
72 int main(){
73     while(scanf("%d",&n)!=EOF){
74         for(int i=1;i<=n;i++){
75             int r,h;
76             scanf("%d %d",&r,&h);
77             a[i]=cake(r,h);
78             v[i]=a[i].V;
79         }
80         solve();
81     }
82     return 0;
83 }