題目鏈接

Snowy Smile

Problem Description

There are n pirate chests buried in Byteland, labeled by 1,2,…,n. The i-th chest's location is (xi,yi), and its value is wi, wi can be negative since the pirate can add some poisonous gases into the chest. When you open the i-th pirate chest, you will get wi value.

You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.

Please write a program to find the best rectangle with maximum total value.

Input

The first line of the input contains an integer T(1≤T≤100), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤2000) in the first line, denoting the number of pirate chests.

For the next n lines, each line contains three integers xi,yi,wi(?109≤xi,yi,wi≤109), denoting each pirate chest.

It is guaranteed that ∑n≤10000.

Output

For each test case, print a single line containing an integer, denoting the maximum total value.

Sample Input

2
4
1 1 50
2 1 50
1 2 50
2 2 -500
2
-1 1 5
-1 1 1

Sample Output

100
6

題意

平面上有n個點，每個點有價值\(w_i\)，可以任意選一個矩形，獲取矩形內(nèi)所有點的值，求最大的價值和為多少

題解

先對所有點坐標離散化，枚舉矩形上界，對于上界及以下的點，以y坐標相等的點為一組，按y從大到小，一組一組的插入線段樹，每插入完一組點，用線段樹求出當(dāng)前的最大子段和，整個過程相當(dāng)于在枚舉矩形上下界，利用線段樹維護最大子段和。

線段樹每個節(jié)點維護：區(qū)間和，左端點向右最大子段和，右端點向左最大子段和，區(qū)間最大子段和，用類似區(qū)間合并的方式合并

#include <bits/stdc++.h>using namespace std; typedef long long ll; const int mx = 2005; const ll INF = 1e18;bool vis[mx][mx];struct Node {int x, y, w;int p, q; }node[mx];vector <int> vx, vy; vector <Node> mp[mx];int getidx(int x) {return lower_bound(vx.begin(), vx.end(), x) - vx.begin() + 1; }int getidy(int y) {return lower_bound(vy.begin(), vy.end(), y) - vy.begin() + 1; }struct Tree {ll sum;ll Lans, Rans, ans; }tree[mx<<2];void pushUp(int rt) {tree[rt].ans = max(max(tree[rt<<1].ans, tree[rt<<1|1].ans), tree[rt<<1].Rans+tree[rt<<1|1].Lans);tree[rt].Lans = max(tree[rt<<1].Lans, tree[rt<<1].sum+tree[rt<<1|1].Lans);tree[rt].Rans = max(tree[rt<<1|1].Rans, tree[rt<<1|1].sum+tree[rt<<1].Rans);tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum; }void build(int l, int r, int rt) {if (l == r) {tree[rt].sum = tree[rt].Lans = tree[rt].Rans = tree[rt].ans = 0;return;}int mid = (l + r) / 2;build(l, mid, rt<<1);build(mid+1, r, rt<<1|1);pushUp(rt); }void update(int pos, int val, int l, int r, int rt) {if (l == r) {tree[rt].sum += val;tree[rt].Lans = tree[rt].Rans = tree[rt].ans = tree[rt].sum;return;}int mid = (l + r) / 2;if (pos <= mid) update(pos, val, l, mid, rt<<1);else update(pos, val, mid+1, r, rt<<1|1);pushUp(rt); }int main() {int T;scanf("%d", &T);while (T--) {vx.clear(); vy.clear();int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d%d%d", &node[i].x, &node[i].y, &node[i].w);vx.push_back(node[i].x);vy.push_back(node[i].y);}sort(vx.begin(), vx.end()); sort(vy.begin(), vy.end());vx.erase(unique(vx.begin(), vx.end()), vx.end());vy.erase(unique(vy.begin(), vy.end()), vy.end());for (int i = 1; i <= n; i++) {node[i].p = getidx(node[i].x);node[i].q = getidy(node[i].y);}for (int i = 1; i <= vy.size(); i++) mp[i].clear();for (int i = 1; i <= n; i++) mp[node[i].q].push_back(node[i]);ll ans = 0;for (int i = 1; i <= vy.size(); i++) {build(1, vx.size(), 1);for (int j = i; j <= vy.size(); j++) {for (int k = 0; k < mp[j].size(); k++) {Node tmp = mp[j][k];update(tmp.p, tmp.w, 1, vx.size(), 1);}ans = max(ans, tree[1].ans);}}printf("%lld\n", ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bpdwn-cnblogs/p/11317316.html

總結(jié)

以上是生活随笔為你收集整理的hdu-6638 Snowy Smile的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。