自动搬运

查看原文

来自洛谷，原作者为

	冷却心 111

搬运于2025-08-24 23:11:23，当前版本为作者最后更新于2025-06-23 17:30:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

花绿青。

超级简单的 dp。记 $f_i$ 表示以 $i$ 结尾的塔的最大美观度。因为要满足严格偏序，所以维护一个指针 $j$ 不停往右移动到最后一个小于 $a_i$ 的位置即可，那么转移是：

• 新开一个序列 $f_i \gets a_i$。
• 任意颜色转移，付出代价 $c$，$\displaystyle f_i \leftarrow \max_{1\le k\le j} f_i + a_i - c$。
• 钦定上一位颜色相同，$\displaystyle f_i \gets \max_{1\le k\le j \wedge w_k = w_i} f_k + a_i$。

第二种转移直接移动指针维护 $\max$，第三种转移对每种颜色统计 $\max$，然后做完了，答案是 $f$ 的最大值。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e5 + 10;
int n, C, W[N]; LL A[N], F[N], tmp[N];

int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> C;
	for (int i = 1; i <= n; i ++) cin >> A[i] >> W[i];
	LL Ans = 0, mx = 0;
	for (int i = 1, j = 0; i <= n; i ++) {
		while (A[j + 1] < A[i]) {
			mx = max(mx, F[++ j]), tmp[W[j]] = max(tmp[W[j]], F[j]);	
		} F[i] = max({F[i], mx - C + A[i], tmp[W[i]] + A[i]}); Ans = max(Ans, F[i]);
	} cout << Ans << "\n";
	return 0;
}