Elma

冷却心 · 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;
}