专栏文章

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

EError_Eric
P11922题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipvjp0y
此快照首次捕获于
2025/12/03 18:38
3 个月前
此快照最后确认于
2025/12/03 18:38
3 个月前
查看原文

Statement

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

Sol

想要边长严格单调只需要 sort 之后将边长相同的一起转移即可。考虑怎么 dp。
记 fif_i 是以 ii 结尾的最大价值，则 fi=max⁡aj<ai{fj−c∗[wi≠wj]}+aif_i = \max_{a_j < a_i}\{f_j - c*[w_i \not = w_j]\} + a_i。这个是 O(n2)O(n^2) 的。
如果不用考虑颜色，那就只需要维护所有 ff 的价值最大的位置 h0h_0。
但是要考虑颜色，那么就对于每个颜色维护一下颜色 ww 的价值最大的位置 gwg_w。以及颜色同 h0h_0 不同的所有位置中，价值最大的位置 h1h_1 就行。
那么只有两个位置可能转移给 fif_i，分别是 gwig_{w_i} 和 h0h_0 （若 h0h_0 颜色相同，则是 gwig_{w_i} 和 h1h_1）。现在单次维护和转移都是 O(1)O(1) 的，因此总共的复杂度是 O(nlog⁡n+n)=O(nlog⁡n)O(n\log n + n) = O(n\log n)，瓶颈在排序。

Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...