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的，用线段树维护比它小的蛋糕的能叠的最大体积，事先离散化，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define PI acos(-1.0)
const int maxn=1e5+;
struct cake{
int r,h;
double V;
cake(){};
cake(int r_,int h_):r(r_),h(h_){V=PI*r*r*h;};
};
struct node{
int l,r;
double maxx;
int mid(){return (l+r)>>;}
};
node tree[maxn<<];
void pushup(int rt){
tree[rt].maxx=max(tree[rt<<].maxx,tree[rt<<|].maxx);
}
void build(int l,int r,int rt){
tree[rt].l=l,tree[rt].r=r;
tree[rt].maxx=;
if(l==r) return ;
int mid=tree[rt].mid();
build(l,mid,rt<<);
build(mid+,r,rt<<|);
}
void update(int index,double C,int L,int R,int rt){
if(L==index&&R==index){
tree[rt].maxx=max(tree[rt].maxx,C);
return ;
}
int mid=tree[rt].mid();
if(index<=mid) update(index,C,L,mid,rt<<);
else update(index,C,mid+,R,rt<<|);
pushup(rt);
}
double query(int l,int r,int L,int R,int rt){
if(L>=l&&R<=r) {
return tree[rt].maxx;
}
double maxx=-1.0;
int mid=tree[rt].mid();
if(l<=mid) maxx=max(maxx,query(l,r,L,mid,rt<<));
if(r>mid) maxx=max(maxx,query(l,r,mid+,R,rt<<|));
return maxx;
}
cake a[maxn];
double v[maxn];
int n;
void solve(){
sort(v+,v++n);
int size=unique(v+,v++n)-v;
double ans=;
build(,size,);
double tmp;
for(int i=;i<=n;i++){
int pos=lower_bound(v+,v+size,a[i].V)-v;
tmp=;
tmp=query(,pos-,,size,);
if(pos-==) tmp=;
tmp+=a[i].V;
ans=max(ans,tmp);
update(pos,tmp,,size,);
}
printf("%.10f\n",ans);
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=;i<=n;i++){
int r,h;
scanf("%d %d",&r,&h);
a[i]=cake(r,h);
v[i]=a[i].V;
}
solve();
}
return ;
}