COGS-2049 疯狂动物城

Description

你意外来到了一个未知的星球，这里是一个动物乌托邦，生活着一群拥有非凡智力的动物.
你遇到了一个叫做尼克的狐狸，他准备给他的 GF 过生日。
他将制作一个巨大的多层蛋糕，他已经有了一些圆柱形的单层蛋糕，可以把这些蛋糕拼
装起来。遗憾的是，由于一些限制，这些单层蛋糕并不能被全部利用，你只能选出一部分来
制作多层蛋糕：

1.物理学要求：为了稳定和美观，半径大的蛋糕必须在放在半径小的蛋糕下面。

2.Mr.Big 的钦定要求：编号小的蛋糕必须放在编号大的蛋糕下面。

作为交换，他将向你介绍黑社会老大 Mr.Big, Mr.Big 会告诉你一些黑科技，这也许是
击败人工智能的关键。
你需要帮他制定一个使多层蛋糕总体积最大的方案，并计算出最大蛋糕的总体积。
注意：两个半径相同的蛋糕不能放在一起。

Input

第一行一个整数 n,
接下来 n 行,第 i+1 行两个整数 R,H 分别表示编号为 i 的蛋糕的半径和高度。

Output

只有一行一个整数，为最大总体积，你需要精确到整数位。

Sample Input

5
10 7
12 1
1 4
9 7
1 1

Sample Output

3983.54

二维偏序稞题，首先按读入顺序更新线段树，以蛋糕半径为下标，以当前此半径为低的最优体积为线段树的值。最终答案为线段树中的最大值。

看到一份优秀的代码，写得比某蒟蒻好得多，发出来供大家参考。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <map>

#include <vector>

#include <queue>

#define ls (x << 1)

#define rs (x << 1 | 1)

#define mid ((l + r) >> 1)

#define L 100010

#define LL long long

const double pi = 3.14159265358979323846;

using namespace std;

inline int gi() {

char cj = getchar();

int ans = , f = ;

while (cj < '' || cj > '') {

if (cj == '-') f = -;cj = getchar();

}

while (cj >= '' && cj <= '') ans = ans *  + cj - '', cj = getchar();

return f * ans;

}

int n, R, r[L], h[L];

LL v[L], tr[L << ], ans;

inline LL query(int x, int l, int r, int a, int b) {

if (a <= l && b >= r) return tr[x];

if (b < l || a > r) return ;

if (b <= mid) return query(ls, l, mid, a, b);

else if (a > mid) return query(rs, mid + , r, a, b);

else return max(query(ls, l, mid, a, mid), query(rs, mid + , r, mid + , b));

}

inline void update(int x, int l, int r, int a, LL w) {

if (l == r) {tr[x] = max(w, tr[x]); return ;}

if (a <= mid) update(ls, l, mid, a, w);

else if (a > mid) update(rs, mid + , r, a, w);

tr[x] = max(tr[ls], tr[rs]);

}

int main() {

//freopen ("zootopia.in","r",stdin);

//freopen ("zootopia.out","w",stdout);

n = gi();

for (int i = ; i <= n; ++i) r[i] = gi(), h[i] = gi(), R = max(R, r[i]);

R++;

for (int i = ; i <= n; ++i) {

LL maxx = query(, , R, r[i] + , R);

v[r[i]] = max(v[r[i]], maxx + h[i] * r[i] * r[i]);

update(, , R, r[i], v[r[i]]);

}

ans = query(, , R, , R);

printf("%.2lf\n", ans * pi);

return ; }

巴特西