Original link:https://www.shuizilong.com/house/archives/codeton-round-5/
Problem E. Tenzing and Triangle
As long as you can write violent dp, you will be 90% successful!
Might as well add up all the points first and consider how much you can optimally save by covering. A useful property that we have found is that the areas covered by the triangles need not overlap, and thus seem to allow simple 1D/1D dynamic programming.
Here we use a tree array, which can maintain the cost of the triangle coverage area.
#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[kx].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*(ij-1));
}
cout << z - f[k] << endl;
}
Further, we put this transfer and separation into the line segment tree to find 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[kx].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;
}
This article is transferred from:https://www.shuizilong.com/house/archives/codeton-round-5/
This site is only for collection, and the copyright belongs to the original author.