题解：P11922 [PA 2025] 叠积木 / Wieża

Error_Eric · 2025-03-19 14:42:44 · 题解

Statement

每个积木块有边长和颜色。每个积木的价值是其边长。每一处相邻的积木，若颜色不同，则有 c 的代价。求所有边长严格单调的积木序列的最大价值。

Sol

想要边长严格单调只需要 sort 之后将边长相同的一起转移即可。考虑怎么 dp。

记 f_i 是以 i 结尾的最大价值，则 f_i = \max_{a_j < a_i}\{f_j - c*[w_i \not = w_j]\} + a_i。这个是 O(n^2) 的。

如果不用考虑颜色，那就只需要维护所有 f 的价值最大的位置 h_0。

但是要考虑颜色，那么就对于每个颜色维护一下颜色 w 的价值最大的位置 g_w。以及颜色同 h_0 不同的所有位置中，价值最大的位置 h_1 就行。

那么只有两个位置可能转移给 f_i，分别是 g_{w_i} 和 h_0 （若 h_0 颜色相同，则是 g_{w_i} 和 h_1）。现在单次维护和转移都是 O(1) 的，因此总共的复杂度是 O(n\log n + n) = O(n\log n)，瓶颈在排序。

Code

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;
const int _= 5.1e5;
int n, c, a[_], col[_], g[_], h[3];
long long f[_];
#define B g[col[i]] // best option with ending of color of i so far
map<int, vector<int>> i_ata;
signed main(){
    ios::sync_with_stdio(0),
    cin.tie(0), cout.tie(0);
    cin >> n >> c;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> col[i], i_ata[a[i]].push_back(i);
    for(auto aval_ixs:i_ata){
        auto aval = aval_ixs.first;
        auto  ixs = aval_ixs.second;
        for(int i:ixs)
            f[i] = max(f[B], f[h[h[0] == B]] - c) + aval;
        for(int i:ixs){
            if(f[i] > f[B]) B = i;
            if(f[i] > f[h[0]]){
                if(col[h[0]] != col[i])
                    h[1] = h[0];
                h[0] = i;
            }
            else if(f[i] > f[h[1]] && col[h[0]] != col[i])
                h[1] = i;
        }

    }
    cout << *max_element(f+1, f+n+1) << endl;
    return 0;
}