Problem E. Tenzing and Triangle

只要能写出暴力 dp 就成功了 90% 啦！

不妨先把所有点都加起来，考虑最优能通过覆盖节省多少。我们发现一个有用的性质是，三角形覆盖的区域，是不需要重叠的，因此似乎可以简单的 1D/1D 动态规划。

这里我们用树状数组，可以维护出三角形覆盖区域的代价。

#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(2e5) + 9;
int n, k, A; vector<PII> P[N]; LL f[N];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif


	RD(n,k,A); LL z = 0;
	REP(i ,n) {
	    int x, y, c; RD(x, y, c);
	    z += c; P[k-x].PB({y, c});
	}

	fenwick_tree<int> T(k+1);

	REP(i, k+1) {
        for (auto p: P[i]) T.add(p.fi, p.se);
        checkMax(f[i], (LL)T.sum(0, i+1) - A*i);
        REP(j, i) checkMax(f[i], f[j] + T.sum(j+1, i+1) - A*(i-j-1));
	}

	cout << z - f[k] << endl;
}

进一步的我们再把这个转移分离分离放到线段树里求 rmq 就好了。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e5) + 9;
const int NN = 4*N;
int n, k, A; vector<PII> P[N]; int f[N];

struct SegTree {
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
#define rt 1,0,k

    int T[NN], D[NN];

    void add(int x, int d) {
        D[x] += d;
        T[x] += d;
    }
    void rls(int x) {
        //return;
        if (D[x]) {
            add(lx, D[x]);
            add(rx, D[x]);
            D[x] = 0;
        }
    }
    void upd(int x) {
        T[x] = max(T[lx], T[rx]);
    }
    void Build(int x, int l, int r) {
        if (l == r) {
            T[x] = A*l;
        } else {
            Build(lc);
            Build(rc);
            upd(x);
        }
    }

    int Add(int x, int l, int r, const int p, const int d) {
        if (l == r) {
            T[x] += d;
        } else {
            rls(x);
            if (p < mr) Add(lc, p, d);
            else Add(rc, p, d);
            upd(x);
        }
    }

    void Add(int x, int l, int r, const int a, const int b, const int d) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            add(x, d);
        } else {
            rls(x);
            Add(lc, a, b, d);
            Add(rc, a, b, d);
            upd(x);
        }
    }

    int Query(int x, int l, int r, const int a, const int b) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) {
            return T[x];
        } else {
            rls(x);
            return max(Query(lc, a, b), Query(rc, a, b));
        }
    }
} T;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif


	RD(n,k,A); int z = 0; REP(i, n) {
	    int x, y, c; RD(x, y, c); z += c;
	    P[k-x].PB({y, c});
	}

	T.Build(rt);

	REP(i, k+1) {
	    if (i) T.Add(rt, i, f[i-1]);
        for (auto p: P[i]) T.Add(rt, 0, p.fi, p.se);
        checkMax(f[i], T.Query(rt, 0, i) - A*i);
	}

	cout << z - f[k] << endl;
}

Posted by xiaodao
Category: 日常