自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 23:13:37，当前版本为作者最后更新于2025-04-14 22:26:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑将最终的局面划分成，若干个极长的，每一列都至少有一个滑动墙的列连续段。设划分出来的连续段是 $[l_1, r_1], [l_2, r_2], \ldots, [l_t, r_t]$，那么不用被解锁的滑动墙的花费是 $\sum\limits_{i = 1}^t g(l_i, r_i)$，其中 $g(l, r)$ 表示所有满足 $l \le l_i \le r_i \le r$ 的滑动墙的 $c_i$ 之和。一种方案合法，当且仅当：

• $\sum\limits_{i = 1}^h c_i - \sum\limits_{i = 1}^t g(l_i, r_i) \le k$，即花费不能超过 $k$；
• 令 $x = \max\limits_{p = 1}^h r_p - l_p + 1$，则 $\exists i \in [1, t], r_i - l_i + 1 \ge x$，因为要给最长的滑动墙留够位置放。

于是我们转而求满足条件的划分方案中，$\sum\limits_{i = 1}^t g(l_i, r_i)$ 的最大值。接下来的 DP 是自然的。设 $f_{i, j, 0/1}$ 表示，考虑到 $[1, i]$ 这个前缀，其中有 $j$ 列没有滑动墙，当前是否出现长度 $\ge x$ 的连续段。有两种转移：

• 第 $i$ 位留空，有 $f_{i, j, k} \gets f_{i - 1, j - 1, k}$；
• 第 $i$ 位是一个连续段的右端点，枚举这个连续段的左端点 $l$，有 $f_{i, j, k \lor [i - l + 1 \ge x]} \gets f_{l - 1, j, k} + g(l, i)$。

朴素转移时间复杂度为 $O(w^3)$，无法通过。考虑优化。发现瓶颈在第二种转移，考虑在最外层枚举 $j$，那么转移形如 $f_i \gets f_{j - 1} + g(j, i)$。考虑线段树优化。线段树每个下标 $j$ 维护 $f_{j - 1} + g(j, i)$，枚举到 $i$ 时加入所有 $r_k = i$ 的滑动墙，即对 $j \in [1, l_k]$ 区间加上 $c_k$。计算 $f_i$ 时求线段树区间最大值即可。

设 $h, w$ 同阶，时间复杂度 $O(w^2 \log w)$。

#include <bits/stdc++.h>
#define fst first
#define scd second
#define pb emplace_back
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 2020;

ll n, m, K, f[maxn][maxn][2];
vector<pii> vc[maxn];

struct node {
	ll l, r, x;
} a[maxn];

struct SGT {
	ll a[maxn << 2], tag[maxn << 2];
	
	inline void pushup(int x) {
		a[x] = max(a[x << 1], a[x << 1 | 1]);
	}
	
	inline void pushtag(int x, ll y) {
		a[x] += y;
		tag[x] += y;
	}
	
	inline void pushdown(int x) {
		if (!tag[x]) {
			return;
		}
		pushtag(x << 1, tag[x]);
		pushtag(x << 1 | 1, tag[x]);
		tag[x] = 0;
	}
	
	void build(int rt, int l, int r) {
		tag[rt] = 0;
		a[rt] = -1e18;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int ql, int qr, ll x) {
		if (ql <= l && r <= qr) {
			pushtag(rt, x);
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, x);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, x);
		}
		pushup(rt);
	}
	
	void modify(int rt, int l, int r, int x, ll y) {
		if (l == r) {
			a[rt] = y;
			return;
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		(x <= mid) ? modify(rt << 1, l, mid, x, y) : modify(rt << 1 | 1, mid + 1, r, x, y);
		pushup(rt);
	}
	
	ll query(int rt, int l, int r, int ql, int qr) {
		if (ql > qr) {
			return -1e18;
		}
		if (ql <= l && r <= qr) {
			return a[rt];
		}
		pushdown(rt);
		int mid = (l + r) >> 1;
		ll res = -1e18;
		if (ql <= mid) {
			res = max(res, query(rt << 1, l, mid, ql, qr));
		}
		if (qr > mid) {
			res = max(res, query(rt << 1 | 1, mid + 1, r, ql, qr));
		}
		return res;
	}
} T[2];

void solve() {
	scanf("%lld%lld%lld", &n, &m, &K);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld%lld", &a[i].l, &a[i].r, &a[i].x);
		vc[a[i].r].pb(a[i].l, a[i].x);
	}
	ll s = 0, mx = 0;
	for (int i = 1; i <= n; ++i) {
		s += a[i].x;
		mx = max(mx, a[i].r - a[i].l + 1);
	}
	mems(f, -0x3f);
	f[0][0][0] = 0;
	for (int j = 0; j <= m; ++j) {
		T[0].build(1, 1, m);
		T[1].build(1, 1, m);
		for (int i = 1; i <= m; ++i) {
			for (int k = 0; k <= 1; ++k) {
				if (j) {
					f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k]);
				}
			}
			T[0].modify(1, 1, m, i, f[i - 1][j][0]);
			T[1].modify(1, 1, m, i, f[i - 1][j][1]);
			for (pii p : vc[i]) {
				T[0].update(1, 1, m, 1, p.fst, p.scd);
				T[1].update(1, 1, m, 1, p.fst, p.scd);
			}
			f[i][j][0] = max(f[i][j][0], T[0].a[1]);
			f[i][j][1] = max({f[i][j][1], T[1].a[1], T[0].query(1, 1, m, 1, i - mx + 1)});
		}
	}
	for (int i = m; ~i; --i) {
		if (s - f[m][i][1] <= K) {
			printf("%d\n", i);
			return;
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}