DDOSvoid's Blog

Luogu P1484 种树

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P1484

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在要求至多选择 $m$ 个数，需满足选择的任意两个数都不相邻，求最大价值

$n\le 5\times 10^5,|a_i|\le 10^6$

Solution

我们考虑反悔自动机，我们令连续若干的只间隔 $1$ 的选择的数为一个选择区间 $[l,r]$($l$ 和 $r$ 一定选)，容易得到选择区间 $[l,r]$ 的长度一定是奇数，我们思考 $[l,r]$ 向外扩展所发生的变化，发现就是将 $[l,r]$ 内选择情况翻转，然后选择 $l-1$ 和 $r+1$，这个时候我们的选择区间从 $[l,r]$ 拓展到了 $[l-1,r+1]$，另外每扩展一次都相当于多选一个点，那么最终答案的结构一定是由若干个选择区间组成，且任意两个选择区间都想距至少 $2$，因为如果相距 $1$ 就是一个选择区间了

我们考虑用大根堆维护每个选择区间向外扩展的价值，每次贪心的选择扩展最大的区间，如果直到扩展完 $m$ 个点也没有两个必选区间相距小于 $2$，那么这肯定就是正确答案了

我们思考如果有两个必选区间相距为 $1$，那么这两个选择区间就相当于合并成了一个选择区间

这个时候我们会发现，区间扩展一定是从 $[l,r]$ 扩展到 $[l - 1, r+1]$ 吗，有没有可能是从 $[l,r]$ 扩展到 $[l - 1,r - 1]$ 呢，容易发现这是不可能发生的，如果 $[l - 1,r-1]$ 的价值大于 $[l,r]$，那么我们就不会到达 $[l,r]$，因为我们可能在 $[l+1,r-1]$ 时就会选择扩展点 $l - 1$ 然后合并成 $[l-1,r-1]$，因为在那个时候，价值最大的是扩展点 $l-1$ 而不是扩展 $[l+1,r-1]$

具体维护选择区间的方法大概就是选择区间 $[l,r]$ 内一个点表示这个选择区间，我们用一个左指针和一个右指针分别指向 $l-1$ 和 $r+1$，另外容易发现如果不管 $a$ 是一个序列还是一个环都不影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <queue>
#define maxn 500010
#define ll long long
using namespace std;

int n, m;
ll a[maxn];

struct node {
    ll v; int k;

    friend bool operator < (const node &u, const node &v) { return u.v < v.v; } 
};

int l[maxn], r[maxn];
bool vis[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; priority_queue<node> Q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; Q.push({ a[i], i });
        l[i] = i - 1; r[i] = i + 1; 
    } ll ans = 0; r[0] = 1; l[n + 1] = n;
    while (m && Q.top().v > 0) {
        node t = Q.top(); Q.pop(); if (vis[t.k]) continue;
        int k = t.k; ans += t.v; --m;
        a[k] = a[l[k]] + a[r[k]] - a[k];
        Q.push({ a[k], k });
        vis[l[k]] = vis[r[k]] = 1;
        l[k] = l[l[k]]; r[k] = r[r[k]]; 
        r[l[k]] = l[r[k]] = k;
    } cout << ans << "\n";
    return 0;
}