题目

★★☆
输入文件：zootopia.in 输出文件：zootopia.out 简单对比

时间限制：1 s 内存限制：32 MB

【题目描述】

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

你需要帮他制定一个使多层蛋糕总体积最大的方案。

你只需要计算出最大的总体积即可。 注意：两个半径相同的蛋糕不能放在一起

【输入格式】

第一行一个整数n,

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

【输出格式】

只有一行一个整数，为最大总体积,由于出题人懒得写评测插件，你需要精确到小数点后2位

题解

思路

此题乍一看是普通的最长上升/下降子序列，然而$O(n^2)$的做法会挂掉，所以要用$O(nlogn)$的做法

DP方程

设为$V(x)$以蛋糕$x$为顶的最大总体积 $V(i)=max(V(i),V(j)+j.v)(j.r>i.r)$ 我们只需要求出$[1,i.r-1]$之间$V$值最大，所以可以用树状数组或者线段树维护。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const double pi = acos(-1); //Thanks to Hzoi_GoFire
struct cake
{
    int r, h;
    inline double v() { return r * r * pi * h; }
};
cake a[maxn];
double dp[maxn];
int n, b[maxn];
//-----------BIT---------------
inline int lowbit(int k) { return k & (-k); }
inline void update(int p, double v)
{
    for (int i = p; i < maxn; i += lowbit(i))
        dp[i] = max(v, dp[i]);
}
inline double maxe(int p)
{
    double ans = 0;
    for (int i = p; i > 0; i -= lowbit(i))
        ans = max(ans, dp[i]);
    return ans;
}
//------------------------------
inline void init()
{
    freopen("zootopia.in", "r", stdin);
    freopen("zootopia.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].r >> a[i].h;
}
//设V[x]为以蛋糕x为顶的最大总体积
//V[i]=max{V[i],V[j]+j.v}(r[j]>r[i])
int main()
{
    init();
    double ans = 0;
    for (int i = n; i > 0; --i)
    {
        double v = maxe(a[i].r - 1) + a[i].v();//O(nlogn)时间求出[1,a[i].r-1]内V最大的元素并加上i.v
        update(a[i].r, v);
        ans = max(ans, v);
    }
    printf("%.2lf\n", ans);
}

最后感谢kZime和Hyoi_algorithm的讲解