自动搬运

查看原文

来自洛谷，原作者为

	Elma_ blog：https://www.cnblogs.com/came11ia

搬运于2025-08-24 21:57:12，当前版本为作者最后更新于2021-02-14 12:11:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易发现挖掉某一个宝藏需要挖掉其上方整个倒三角内的所有方块，我们假设这个倒三角在 $y=-1$ 上的左右端点为 $l,r$，那么这个宝藏在 $x$ 轴上的映射为区间 $[l,r]$。进一步我们可以发现，宝藏的位置和 $x$ 轴上的区间是一一对应的。

对于一个宝藏，我们可以在 $O(1)$ 求出其在 $x$ 轴上的区间 $[l,r]$ 和单独挖出这一个宝藏的代价 $w$。如果一个区间被另一个区间完全包含，那么显然选了大的区间就会自动加上小区间的贡献，因此我们可以预处理出每个区间与其完全包含的区间的贡献和，这一部分的时间复杂度为 $O(n^2)$。

之后是一个比较套路的 dp，设 $f_i$ 为前 $i$ 个宝藏中必选 $i$ 的最大利润，从前往后枚举 $j$：

• 若 $j$ 区间与 $i$ 区间无交，直接加上 $j$ 的利润；
• 若 $j$ 区间被 $i$ 区间完全包含，贡献已经预处理，直接跳过；
• 若 $j$ 区间与 $i$ 区间有交，因为交的代价被减了两次，加上 $j$ 的利润后再加上交的部分的代价；

然后你会发现这个 dp 是有问题的，考虑一种情况，假设对于 $i$ 区间现在枚举到 $j$，而 $i$ 区间与 $j$ 区间的交完全包含了某个区间 $k$，显然 $i$ 和 $j$ 都完全包含 $k$，那么 $k$ 的贡献就会被重复计算。因此在 dp 的时候，对于 $i,j$ 有交的情况，我们还需要计算被 $i,j$ 的交所完全包含的区间的贡献和，然后减去这个值。

如果每次 dp 都暴力去找这些区间的话时间复杂度是 $O(n ^ 3)$ 的。考虑优化找这些区间的过程，我们首先对所有区间以 $r$ 为第一关键字，$l$ 为第二关键字排序，那么在枚举 $j$ 的过程中右端点一定单调不降，交的部分右端点也一定单调不降，因此转移的时候直接拿一个指针指向要计算的区间，不断右移指针就可以了。时间复杂度为 $O(n^2)$。

#include <map>
#include <ctime>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
inline int read() {
	int x = 0, w = 1;char ch = getchar();
	while (ch > '9' || ch < '0') { if (ch == '-')w = -1;ch = getchar(); }
	while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();
	return x * w;
}
inline void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
 
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;
 
inline int min(int x, int y) { return x < y ? x : y; }
inline int max(int x, int y) { return x > y ? x : y; }

struct node {
    int l, r, v1, v2, w;
    bool operator < (const node p) const {
        return r == p.r ? l < p.l : r < p.r;
    }
} a[maxn];
int n, ans, cnt, pos, f[maxn];

inline int calc(int l, int r) {
    int delta = (l + r) & 1;
    return (r - l + 2 + delta) * (r - l + 2 - delta) / 4;
}

int main() {
    n = read();
    for (int i = 1, x, y; i <= n; i++) {
        x = read(), y = read();
        a[i].l = x + y + 1, a[i].r = x - y - 1;
        a[i].v1 = read(), a[i].w = calc(a[i].l, a[i].r);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) 
            if (a[i].l <= a[j].l && a[j].r <= a[i].r)
                a[i].v2 += a[j].v1;
    sort(a + 1, a + n + 1);
    for (int i = 1, val;i <= n;i++) {
        f[i] = val = a[i].v2 - a[i].w, pos = 1, cnt = 0;
        for (int j = 1, tmp; j < i; j++) {
            if (a[j].r >= a[i].l && a[j].l < a[i].l) {
                while (pos <= i && a[pos].r <= a[j].r) {
                    if (a[pos].l >= a[i].l) cnt += a[pos].v1;
                    pos++;
                }
                tmp = calc(a[i].l, a[j].r);
                f[i] = max(f[i], f[j] + val + tmp - cnt);
            }
            else if (a[j].r < a[i].l) f[i] = max(f[i], f[j] + val);
        }
    }
    for (int i = 0;i <= n;i++) ans = max(f[i], ans);
    printf("%d\n", ans);
	return 0; 
}