P7219 反贪做法证明

· · 题解

反贪真是个美妙的东西，可惜目前没有找到任何一个靠谱的证明。

@small_lemon_qwq 给出的 GPT 证明，由我验证了正确性，简化了表述然后放到了这里。

直接贪心（假的）：从下往上扫，每次看这个点会和当前最优解中的哪些点冲突，如果删掉这个点代价更小就删掉这个点，否则删掉当前最优解中和它冲突的所有点。

反悔贪心：这篇题解做法。具体来讲，按照 Y 从小到大排序，i\sim j 意思是 j 和 i 冲突的点，w_i=\displaystyle\sum_{\substack{j<i\\i\sim j}}\max(0,c_j-w_j)，答案为 \displaystyle\sum\min(c_i,w_i)。

证明：

首先 i\sim j\iff \max\limits_{\min(X_i,X_j)\le k\le \max(X_i,X_j)} A_k<\min(Y_i,Y_j)。我们按照 Y 排序，所以 i<j\Longrightarrow Y_i\le Y_j。有下面显然的引理。

引理 1：若 i<j,i<k,i\sim j,i\sim j，则一定有 j\sim k。证明是显然的，只需要分类讨论 X_i,X_j,X_k 的大小关系。

构造冲突图 G，两点有边等价于两点冲突，点权为 C_i。

我们设 K_i=\{i\}\cup \{j>i\mid i\sim j\}。

定理 1：K_i 是 G 上的团（即 \forall i,\forall j,k\in K_i,j\sim k）。由引理 1 显然。

定理 2：答案是 \sum C-\operatorname{MWIS}(G)，其中 \operatorname{MWIS}(G) 是 G 上的最大权独立集权值。显然。

定理 Meow：设 A 是反悔贪心得到的答案，则最优解（即答案）不优于 A。

证明：

首先设 d_i=\max(0,c_i-w_i)，则 w_i=\displaystyle\sum_{\substack{j<i\\i\sim j}}d_j。注意到 \min(c_i,w_i)=c_i-d_i，所以反贪得到的答案是 A=\sum c-\sum d。我们只需要证明最大独立集权值不可能超过 \sum d 即可。

显然有 c_i\le d_i+w_i，展开 w_i 得到 c_i\le d_i+\displaystyle\sum_{\substack{j<i\\j\sim i}}d_j。注意到 (j<i\land j\sim i)\lor j=i\iff i\in K_j。所以 w_i\le \displaystyle\sum_{i\in K_j}d_j。

假设 S 是一个独立集，则其权值为 \displaystyle\sum_{i\in S}c_i，由上面的不等式有 \displaystyle\sum_{i\in S}c_i\le \sum_{i\in S}\sum_{i\in K_j}d_j=\sum_j d_j\sum_{i\in S,i\in K_j}1=\sum_j d_j\lvert S\cap K_j\rvert。注意到 K_j 是团而 S 是独立集，所以 \lvert S\cap K_j\rvert\le 1。所以 \displaystyle\sum_{i\in S}c_i\le \sum d，证毕。

定理 Final：答案为 A。证明：首先不会优于 A，其次反贪可以给出一个解。\square

综上我们证明了反贪做法的正确性。

:::info[rec&code]

rec。

#include <cstdio>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

bitset<200005> bs;

class star
{
public:
    int x, y, c;
} stars[200005];

class dsu
{
public:
    int fa[200005], rk[200005];
    int getfa(int x) { while(x != fa[x]) x = fa[x] = fa[fa[x]]; return x; }
    void merge(int x, int y) { if((x = getfa(x)) == (y = getfa(y))) return; if(rk[x] < rk[y]) fa[x] = y; else if(rk[x] > rk[y]) fa[y] = x; else { fa[x] = y; rk[y]++; }}
} dk;

int vl[200005], vr[200005];
vector<int> ktop[200005];

class fenwick
{
public:
    long long st[200005];
    void vadd(int pos, long long val, int n) { do { st[pos] += val; } while((pos += pos & -pos) <= n); }
    long long qsum(int pos) { long long sum = 0; do { sum += st[pos]; } while(pos -= pos & -pos); return sum; }
} fw;

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        dk.fa[i] = i;
        vl[i] = i+1;
        vr[i] = i-1;
        int a;
        scanf("%d", &a);
        ktop[a].push_back(i);
    }
    vl[0] = 1; vr[n+1] = n; dk.fa[n+1] = n+1;
    int m;
    scanf("%d", &m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d", &stars[i].x, &stars[i].y, &stars[i].c);
    }
    sort(stars + 1, stars + m + 1, [](const auto &x, const auto &y) { return x.y < y.y; });
    int cur = 0;
    long long sum = 0;
    for(int i=1;i<=m;i++)
    {
        while(cur + 1 < stars[i].y)
        {
            for(int x : ktop[++cur])
            {
                int ll = vl[dk.getfa(x-1)], rr = vr[dk.getfa(x+1)];
                if(bs[x-1]) dk.merge(x, x-1);
                if(bs[x+1]) dk.merge(x, x+1);
                bs[x] = true;
                vl[dk.getfa(x)] = ll; vr[dk.getfa(x)] = rr;
            }
        }
        int gr = vr[dk.getfa(stars[i].x)], gl = vl[dk.getfa(stars[i].x)];
        long long w = fw.qsum(stars[i].x);
        long long d = max(0ll, stars[i].c - w);
        sum += stars[i].c - d;
        fw.vadd(gl, d, n); fw.vadd(gr + 1, -d, n);
    }
    printf("%lld\n", sum);
    return 0;
} // luogu://article/rrie56rp

:::