HDU 6638 - Snowy Smile

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6638

传统DP的做法是用一个数组 r[u] 来维护一个行前缀和，r[u] 表示当第 \(i\) 行到第 \(j\) 行第 \(u\) 列所有元素相加的和，然后转化为一味的最大子段和，复杂度 \(O(n^3)\)。

而对于题目中给出的稀疏矩阵而言，离散化之后，如果我们用线段树维护 r[u]，我们发现线段树最多做两千次单点更新，均摊下来每个点的复杂度很小，复杂度 \(O(n^2 \log n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int MAX_N = 2000 + 5;
const LL INF = LL(1E18);
int T, n, x[MAX_N], y[MAX_N], w[MAX_N];
int idx[MAX_N], idy[MAX_N], totX, totY;
vector <PII> r[MAX_N];
LL pre[MAX_N];
inline int getId(char sel, int u) {
    if (sel == 'x') return lower_bound(idx + 1, idx + totX + 1, u) - idx;
    if (sel == 'y') return lower_bound(idy + 1, idy + totY + 1, u) - idy;
}
// Segment Tree
LL sum[MAX_N * 4], lSum[MAX_N * 4], rSum[MAX_N * 4], mSum[MAX_N * 4];
inline int ls(int o) {
    return o << 1;
}
inline int rs(int o) {
    return o << 1 | 1;
}
inline void pushUp(int o) {
    sum[o] = sum[ls(o)] + sum[rs(o)];
    lSum[o] = max(lSum[ls(o)], lSum[rs(o)] + sum[ls(o)]);
    rSum[o] = max(rSum[rs(o)], rSum[ls(o)] + sum[rs(o)]);
    mSum[o] = max(max(mSum[ls(o)], mSum[rs(o)]), rSum[ls(o)] + lSum[rs(o)]);
}
void build(LL *a, int o, int l, int r) {
    if (l == r) {
        sum[o] = a[l];
        mSum[o] = lSum[o] = rSum[o] = max(LL(-INF), a[l]);
        return;
    }
    int mid = (l + r) >> 1;
    build(a, ls(o), l, mid);
    build(a, rs(o), mid + 1, r);
    pushUp(o);
}
void update(int o, int l, int r, int pos, LL v) {
    if (l == r) {
        sum[o] = v;
        mSum[o] = lSum[o] = rSum[o] = max(LL(-INF), v);
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(ls(o), l, mid, pos, v);
    if (pos > mid) update(rs(o), mid + 1, r, pos, v);
    pushUp(o);
}
LL query(int o, int l, int r, int L, int R) {
    if (L <= l && R >= r) {
        return mSum[o];
    }
    int mid = (l + r) >> 1;
    LL ret = -INF;
    if (R >= mid) ret = max(ret, query(ls(o), l, mid, L, R));
    else if (L < mid) ret = max(ret, query(rs(o), mid + 1, r, L, R));
    else {
        ret = max(query(ls(o), l, mid, L, R), query(rs(o), mid + 1, r, L, R));
        ret = max(ret, rSum[ls(o)] + lSum[rs(o)]);
    }
    return ret;
}
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d%d%d", x + i, y + i, w + i);
        totX = totY = 0;
        for (int i = 1; i <= n; ++i) idx[++totX] = x[i], idy[++totY] = y[i];
        sort(idx + 1, idx + totX + 1); sort(idy + 1, idy + totY + 1);
        totX = unique(idx + 1, idx + totX + 1) - (idx + 1);
        totX = unique(idy + 1, idy + totY + 1) - (idy + 1);
        int xMax = 0, yMax = 0;
        for (int i = 1; i <= n; ++i) xMax = max(xMax, getId('x', x[i])), yMax = max(yMax, getId('y', y[i]));
        for (int i = 1; i <= xMax; ++i) r[i].clear();
        for (int i = 1; i <= n; ++i) r[getId('x', x[i])].push_back({getId('y', y[i]), w[i]});
        LL maxAns = -INF;
        for (int i = 1; i <= xMax; ++i) {
            memset(pre, 0, sizeof pre);
            build(pre, 1, 1, yMax);
            for (int j = i; j <= xMax; ++j) {
                for (auto const &e: r[j]) pre[e.first] += e.second, update(1, 1, yMax, e.first, pre[e.first]);
                maxAns = max(maxAns, mSum[1]);
            }
        }
        printf("%lld\n", maxAns);
    }
    return 0;
}