D. Babaei and Birthday Cake

题目链接

Codeforces Round #343 (Div. 2)--D. Babaei and Birthday Cake

题解

中档题。题意大概是求一个最长上升序列,只不过数据规模比较大。
对于一般规模的题目直接正常的最长上升序列dp即可,但是因为这一题的数据规模比较大,需要结合线段树进行查询和修改。

代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXNUM = 100005;
const double PI = acos(-1.0);

struct Node {
    int l, r;
    long long Max;
}node[MAXNUM * 4];
long long v[MAXNUM];
long long a[MAXNUM];

void build(int id, int l, int r) {
    int mid = (l + r) >> 1;
    node[id].l = l;
    node[id].r = r;
    if (l == r) {
        node[id].Max = 0;
        return;
    }
    build(id << 1, l, mid);
    build((id << 1) | 1, mid + 1, r);

    node[id].Max = max(node[id << 1].Max, node[(id << 1) | 1].Max);
}

void update(int id, int k, long long p) {
    int mid = (node[id].l + node[id].r) >> 1;

    if (node[id].l == node[id].r) {
        node[id].Max = p;
        return;
    }

    if (k <= mid) update(id << 1, k, p);
    else update((id << 1) | 1, k, p);
    node[id].Max = max(node[id << 1].Max, node[(id << 1) | 1].Max);
}

long long query(int id, int l, int r) {
    int mid = (node[id].l + node[id].r) >> 1;

    if (l > r) return 0;

    if (node[id].l == l && node[id].r == r)
        return node[id].Max;
    else if (r <= mid)
        return query(id << 1, l, r);
    else if (l > mid)
        return query((id << 1) | 1, l, r);
    else
        return max(query(id << 1, l, mid), query((id << 1) | 1, mid + 1, r));
}

int main()
{
    int n;
    cin >> n;
    long long r, h;
    for (int i = 1; i <= n; i++) {
        scanf("%I64d%I64d", &r, &h);
        v[i] = r * r*h;
        a[i] = v[i];
    }

    sort(a + 1, a + n + 1);
    long long ans = 0;
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int loc = lower_bound(a + 1, a + n + 1, v[i]) - a;
        long long nowMax = max(v[i], query(1, 1, loc - 1) + v[i]);
        update(1, loc, nowMax);
        ans = max(ans, nowMax);
    }
    printf("%.10f\n", ans*PI);

    return 0;
}

标签: dp, data structures

添加新评论