种树-优先队列

洛谷 P1792 种树

思路

我们考虑单个树坑，若此树坑被选择，则两侧树坑都不可选；
会存在某种情况，选择两侧的树坑带来的总收益大于此树坑，我们就可以在选择此树坑时向优先队列中加入“后悔项”，权重是其左右两侧的树坑之和减去该树坑（$v[i-1]+v[i+1]-v[i]$）；

普适来说，我们构造一种“评价块”，其满足以下性质：

1. 其长度为奇数；
2. 其左右端点树坑均认为被种植，并以此隔一种一；
3. 其权值为区间内所有被种植-未种植，即（$\sum_{i被种植}v_i-\sum_{j未种植}v_j$）；
4. 其区间内所有子评价块均不独立参与优先队列；
5. 任意评价块被贪心接受后，都使得总种植数+1；
6. 所有独立的评价块的并集为整个环，交集为空；

我们对于这样的评价块，采取这样的策略：

1. 初始化每个树坑为单独的评价块，权值为树坑的美观值，加入优先队列进行贪心；
2. 若队顶评价块不独立，则抛出，直至队顶树坑独立；
3. 将独立的队顶评价块吸收，并建立对应的新评价块（后悔快），新块的范围为本块及左右两相邻块，权值为相邻块权值之和减去本块，并做好不独立和相邻标记；

如此循环 m 次即可；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e7;
const ll M = 1e9 + 7;
struct prt
{
    int v, tl, tr;
} p[200005];
bool vis[200005]; //独立标记
priority_queue<pair<int, int>> pue;
int main()
{
    int n, m, ans = 0;
    cin >> n >> m;
    if (n < m * 2)
    {
        printf("Error!");
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i].v);
        p[i].tr = i + 1;
        p[i].tl = i - 1;
        pue.push({p[i].v, i});
    }
    p[1].tl = n, p[n].tr = 1; //特殊处理首末块
    for (int i = 1; i <= m; i++)
    {
        while (vis[pue.top().second])
            pue.pop(); //清空非独立块
        pair<int, int> now = pue.top();
        pue.pop();
        ans += now.first;
        // printf("%d %d %d\n",now.second,p[now.second].tl,p[now.second].tr);
        vis[p[now.second].tl] = vis[p[now.second].tr] = 1; //左右不再独立
        p[now.second].v =
            p[p[now.second].tl].v + p[p[now.second].tr].v - p[now.second].v; //构建新块权值
        p[now.second].tl = p[p[now.second].tl].tl;                       //更新左右临块
        p[now.second].tr = p[p[now.second].tr].tr;                       //
        p[p[now.second].tl].tr = now.second;                             //
        p[p[now.second].tr].tl = now.second;                             //
        pue.push({p[now.second].v, now.second});
    }
    cout << ans;
}

ED

\