Codeforces 629D Babaei and Birthday Cake

发表于 分类于 Disqus：

链接

传送门

题意

给出\(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;
}
相关文章