There are?nn?pirate chests buried in Byteland, labeled by?1,2,…,n1,2,…,n. The?ii-th chest's location is?(xi,yi)(xi,yi), and its value is?wiwi,?wiwi?can be negative since the pirate can add some poisonous gases into the chest. When you open the?ii-th pirate chest, you will get?wiwi?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.

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

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

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

It is guaranteed that?∑n≤10000∑n≤10000.OutputFor 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

SOLUTION:
都是都是套路，每次枚舉矩形的上邊界
然后每個下邊界加入線段樹后，查詢最大字段和。

CODE:
#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long ll;const int N = 2005;struct T{ll x, y, w;T(){}T(ll x, ll y, ll w): x(x), y(y), w(w){} }a[N];bool cmp(const T& a, const T& b) {return a.x < b.x; }int b[N];struct {int l, r;ll lx, rx, mx;ll sum; }tree[N << 2];void build(int k, int l, int r) {tree[k].l = l;tree[k].r = r;tree[k].sum = tree[k].lx = tree[k].rx = tree[k].mx = 0;if(l == r)return;int mid = (l + r) / 2;build(2*k, l, mid);build(2*k + 1, mid + 1, r); }void push_up(int k) {tree[k].sum = tree[2*k].sum + tree[2*k+1].sum;tree[k].lx = max(tree[2*k].lx, tree[2*k].sum + tree[2*k+1].lx);tree[k].rx = max(tree[2*k+1].rx, tree[2*k+1].sum + tree[2*k].rx);tree[k].mx = max(max(tree[2*k].mx, tree[2*k+1].mx), tree[2*k].rx + tree[2*k+1].lx); }void insert(int k, int x, int w) {if(tree[k].l == tree[k].r){tree[k].sum = tree[k].lx = tree[k].rx = tree[k].mx = tree[k].mx + w;return;}int mid = (tree[k].l + tree[k].r) / 2;if(x <= mid)insert(2*k, x, w);elseinsert(2*k+1, x, w);push_up(k); }inline ll query() {return tree[1].mx; }int main() {ios::sync_with_stdio(false);int t;cin >> t;while(t --){int n;cin >> n;for(int i = 1; i <= n; i ++){ll x, y, w;cin >> x >> y >> w;a[i] = T(x, y, w);b[i] = y;}sort(b + 1, b + n + 1);int k = unique(b + 1, b + n + 1) - b - 1;for(int i = 1; i <= n; i ++){int y = lower_bound(b + 1, b + k + 1, a[i].y) - b;a[i].y = y;}sort(a + 1, a + n + 1, cmp);ll ans = 0;for(int i = 1; i <= n; i ++){if(i != 1 && a[i].x == a[i - 1].x)continue;build(1, 1, k);for(int j = i; j <= n; j ++){if(j != i && a[j].x != a[j - 1].x)ans = max(ans, query());insert(1, a[j].y, a[j].w);}ans = max(ans, query());}cout << ans << endl;}return 0; }

　　

轉載于:https://www.cnblogs.com/zhangbuang/p/11386932.html

總結

以上是生活随笔為你收集整理的【HDU2019多校】E - Snowy Smile (最大字段和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。