CF1842E Tenzing and Triangle 题解

六楼溜刘 · 2023-06-25 20:49:11 · 题解

题意

现在在平面直角坐标系内有 n 个点，每个点有一个权值 w_i，对于所有点 (x_i,y_i)，有 0 \le x_i,y_i,x_i+y_i < k。
现在丁真想要删除这个平面上的所有点，有两种删点的方法：
1. 直接删掉某个点，代价为该点的权值 w_i。
2. 任意选择一个点 (x_0,y_0)（不一定在原来的点集中），需要保证 0 \le x_0,y_0,x_0+y_0 < k，删除所有满足 x_i \ge x_0 且 y_i\ge y_0 的点，即删除这个点与函数 y=-x+k 的图像围成的等腰直角三角形中所有点。代价为三角形直角边长 l\times A。
两个操作可以执行任意次，求删除所有点的最小代价。

题解

这道题赛时想了个贪心伪掉了。

首先容易证明假如有两个三角形重合了必定不优：

在左图中，原本两个三角形只覆盖了绿色区域，不仅没有覆盖到黄色区域，代价还比红色三角形大，故两个黑色三角形必定不优，另外像右图一样只有一点重合的也不优，证明同理。

然后还有一个转化，假设所有点都用操作一删除，然后每次一个对 (x_0,y_0) 操作二就会对答案产生 l\cdot A-s(x_0,y_0) 的贡献，其中 s(x_0,y_0) 表示点 (x_0,y_0) 围出的三角形中所有点的权值和。原来的代价和就转化为了 \left(\sum y_i\right)+\left[\sum l\cdot A-s(x_0,y_0)\right]。我们的问题就转化成了求 \sum h(x_0,y_0)=l\cdot A-s(x_0,y_0) 的最小值。

容易想到 dp，设 dp_i 表示所有 x_0 \ge i 的操作二的 h 的和的最小值。

假设有一个操作二 x_0=i，这个三角形直角边长为 len（如果没有那么 len=0），易得转移方程：

dp_i=\min_{len=0}^{k-i}\{dp_{i+len+1}+len\cdot A +s(i,k-i-len)\}

由于重合了不优所以要从 dp_{i+len+1} 转移过来（而不是 dp_{i+len}，不然就重合了），后面的都很好理解，自己画图推一推。

发现 dp_{i+len+i} 看起来很烦，考虑设 j=i+len+1，那么 len=j-i-1，易得转移方程：

dp_i=\min_{j=i+1}^{k+1}\{dp_{j}+(j-i-1)\cdot A +s(i,k-j+1))\}

这里 k+1 就是一个边界，不用管它。

然后我们把和 i 相关的提出来：

dp_i=\min_{j=i+1}^{k+1}\{dp_{j}+(j-1)\cdot A +s(i,k-j+1))\}-i\cdot A

对于一个特定的 i，设 g(j)=dp_{j}+(j-1)\cdot A +s(i,k-j+1))，那么就变成了：

dp_i=\min_{j=i+1}^{k+1}\{g(j)\}-i\cdot A

现在难点就是对 s(i,k-j+1) 的处理，对于一个操作二，我们很难求出点的权值和，不妨反过来想，一个权值为 w 的点会影响多少个 g(j)。

假设有一个点坐标为 (i,y)，那么对于所有横坐标小于等于 i，纵坐标小于等于 y 的操作二都会产生影响，这样的操作二所对应的 g(j) 必定满足 j \ge k-y+1，并且所有满足 j \ge k-y+1 的 j 都必定会被影响，原因显然。

那么就可以用一棵线段树维护 g(j) 的区间加，转移的时候区间取最小值，具体见代码。

code

//author: six-floor-slip-liu

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=2e5+5,inf=1e18;
i64 n,k,a,ans;
struct Node{
    i64 x,y,cst;
}s[N];
bool cmp(Node a,Node b){
    if(a.x!=b.x) return a.x>b.x;
    return a.y>b.y;
}
i64 dp[N];
struct SegmentTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 querymin[N<<2],mark[N<<2];
    void PushUp(i64 id){//回溯
        querymin[id]=min(querymin[id<<1],querymin[id<<1|1]);
    }
    void PushDown(i64 id){//下传懒标记
        querymin[id<<1|1]+=mark[id];
        querymin[id<<1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        mark[id<<1]+=mark[id];
        mark[id]=0;
    }
    void QueryAdd(i64 L,i64 R,i64 X,i64 l=0,i64 r=k+1,i64 id=1){
    //区间加
        if(L<=l&&r<=R){
            querymin[id]+=X;
            mark[id]+=X;
            return;
        }
        if(mark[id]&&l<r) PushDown(id);
        if(L<=mid) QueryAdd(L,R,X,lson);
        if(mid< R) QueryAdd(L,R,X,rson);
        PushUp(id);
    }
    i64 AskMin(i64 L,i64 R,i64 l=0,i64 r=k+1,i64 id=1){
    //区间取最小值
        if(L<=l&&r<=R){
            return querymin[id];
        }
        if(mark[id]&&l<r) PushDown(id);
        i64 res=inf;
        if(L<=mid) res=min(res,AskMin(L,R,lson));
        if(mid< R) res=min(res,AskMin(L,R,rson));
        PushUp(id);
        return res;
    }
}mt;
signed main(){
    n=read();k=read();a=read();
    forup(i,1,n){
        s[i].x=read();s[i].y=read();s[i].cst=read();
        ans+=s[i].cst;
    }
    sort(s+1,s+n+1,cmp);
    i64 l=1;
    mt.QueryAdd(k+1,k+1,k*a);//先上传边界
    fordown(i,k,0){
        while(s[l].x==i){//把所有 x=i 的全部上传
            mt.QueryAdd(k-s[l].y+1,k+1,-s[l].cst);
            ++l;
        }
        dp[i]=min(0ll,mt.AskMin(i+1,k+1)-i*a);
        mt.QueryAdd(i,i,dp[i]+(i-1)*a);
        //单点上传 dp[j]+(j-1)*A，s 放到后面处理。
    }
    printf("%lld",ans+dp[0]);//注意加上权值总和。
}