Codeforces 629D Babaei and Birthday Cake

链接

传送门

题意

给出$n$个圆柱形蛋糕的底面半径$r$和高度$h$。要将蛋糕放在桌子上,后面的蛋糕可以放在前面的比它小的蛋糕上,或者放到桌子上。输出放在一起的蛋糕的最大总体积。

思路

计算蛋糕的体积并排序,然后目标转化为求上升子序列和的最大值。得到状态转移方程$d[i]=max(d[j],j<i,V[j]<V[i])+V[i]$。为了求出$max(d[j],j<i,V[j]<V[i])$,使用线段树储存$d[i]$的值,保存每个节点的原始序列位置$p[i]$,每次查询,区间$[0,p[i]]$的最大值。然后更新$p[i]$节点的值为$d[i]$。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const double PI = acos(-1);
const int maxn = 100010;
int n;
LL q[maxn << 2], d[maxn];
struct node {
LL v;
int p;
bool operator < (const node& rhs) const {
return v < rhs.v || (v == rhs.v && p > rhs.p);
}
} a[maxn];
void update(int idx, LL x, int id = 1, int b = 0, int e = n) {
if (idx < b || idx >= e) {
return;
}
if (idx == b && e - b == 1) {
q[id] = d[b] = x;
return;
}
int mid = (b + e) >> 1, l = id << 1, r = l | 1;
if (idx < mid) {
update(idx, x, l, b, mid);
}else{
update(idx, x, r, mid, e);
}
q[id] = max(q[l], q[r]);
}
LL query(int ql, int qr, int id = 1, int b = 0, int e = n) {
if (ql >= e || qr <= b) return 0;
if (ql <= b && e <= qr) return q[id];
int mid = (b + e) >> 1, l = id << 1, r = l | 1;
return max( query(ql, qr, l, b, mid), query(ql, qr, r, mid, e) );
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int r, h;
scanf("%d%d", &r, &h);
a[i].v = LL(r) * r * h;
a[i].p = i;
}
sort(a, a + n);
for (int i = 0; i < n; ++i) {
int idx = a[i].p;
d[idx] = query(0, idx) + a[i].v;
update(idx, d[idx]);
}
printf("%.10f\n", query(0, n) * PI);
return 0;
}

支付宝扫码领红包