Description

Input

第一行是用空格隔开的二个正整数, 分别给出了舞台的宽度 \(W\) 和馅饼的个数 \(n\). 接下来 \(n\) 行, 每一行给出了一块馅饼的信息. 由三个正整数组成, 分别表示了每个馅饼落到舞台上的时刻 \(t_i\), 掉到舞台上的格子的编号 \(p_i\), 以及分值 \(v_i\). 游戏开始时刻为 \(0\).

输入文件中同一行相邻两项之间用一个空格隔开. 输入数据中可能存在两个馅饼的 \(t_i\) 和 \(p_i\) 都一样.

Output

一个数, 表示游戏者获得的最大总得分.

Sample Input

3 4
1 2 3
5 2 3
6 3 4
1 1 5

Sample Output

12

Data Range

对于所有数据, 满足:\(1 \leq W \leq 10^8, 1 \leq n \leq 10^5, 1 \leq t_i \leq 10^8, 1 \leq p_i \leq W, 1 \leq v_i \leq 1000\)

Explanation

首先这个如果是 \(O(n^2)\) 的动归很好写对吧...... 明明就是水的 DP~


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 100100;

struct pie {
    lli t, p, v;
    friend bool operator < (pie a, pie b) {
        return a.t < b.t;
    }
};

int n, w;
lli dp[maxn];
pie arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &w, &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld%lld", &arr[i].t, &arr[i].p, &arr[i].v);
    // Aligning time to grid
    sort(arr + 1, arr + n + 1);
    // Naive!(TH) dynamic programming
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        for (int j = 1; j < i; j++)
            if (abs(arr[i].p - arr[j].p) <= 2 * (arr[i].t - arr[j].t))
                dp[i] = max(dp[i], dp[j]);
        dp[i] += arr[i].v;
    }
    // Get result
    lli res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, dp[i]);
    printf("%lld\n", res);
    return 0;
}

然后我们来考虑优化到 \(O(n \log n)\) 的事情:

其实正解的做法, 就是把所有的坐标离散化然后 再次用树状数组维护一下......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 100100;

struct pie {
    lli t, p, v;
    lli x, y; // Maintainers
    friend bool operator < (pie a, pie b) {
        if (a.x == b.x)
            return a.y > b.y;
        return a.x < b.x;
    }
};

class BinaryIndexedTree
{
public:
    int n;
    lli data[maxn];
    void change(int x, lli val) {
        for (int i = x; i <= n; i += i & -i)
            data[i] = max(data[i], val);
        return ;
    }
    lli query(int x) {
        lli res = 0;
        for (int i = x; i > 0; i -= i & -i)
            res = max(res, data[i]);
        return res;
    }
    void init(int n) {
        this->n = n;
        memset(data, 0, sizeof(data));
        return ;
    }
} bit;

int n, w;
lli dp[maxn];
lli y_axis[maxn]; // Temporary array
pie arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &w, &n);
    arr[0].x = arr[0].y = arr[0].t = -w;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld%lld", &arr[i].t, &arr[i].p, &arr[i].v);
        arr[i].t *= 2;
        arr[i].x = arr[i].t + arr[i].p;
        arr[i].y = arr[i].t - arr[i].p;
    }
    // Aligning time to grid
    sort(arr, arr + n + 1);
    // Descatterizing y-axis
    for (int i = 0; i <= n; i++)
        y_axis[i] = arr[i].y;
    sort(y_axis, y_axis + n + 1);
    for (int i = 0; i <= n; i++)
        arr[i].y = lower_bound(y_axis, y_axis + n + 1, arr[i].y) - y_axis + 1;
    // Maintaining dynamic programming with BIT
    bit.init(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = arr[i].v + bit.query(arr[i].y);
        bit.change(arr[i].y, dp[i]);
    }
    // Get result
    lli res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, dp[i]);
    printf("%lld\n", res);
    return 0;
}