很多題解都是簡單帶過，所以打算自己寫一篇，順便也加深自己理解

?

前置知識：線段樹、線段樹維護最大字段和、二維坐標離散化

?

題解：

1.很容易想到我們需要枚舉所有子矩陣來得到一個最大子矩陣，所以我們的任務是 “枚舉所有子矩陣”，

　二維前綴和暴力枚舉達到O(n^4),? DP結合前綴和枚舉也需要O(n^3)，然而我們的時間需要更少.

?

2.可以看到坐標范圍為 -10^9~10^，但是點 n<=2000個，所以我們需要先將點 離散化。

?

3.將點 按y軸高度排序，枚舉矩陣的上下界，這將達到O(n^2)了。

?

4.最重點的一步，將矩陣內的點 加入線段樹維護。下面解釋下這一步。

　首先假設我們枚舉的這一個矩陣的 上界為 up ,下界為 down ，目前的矩陣的寬度就已經知道是 up-down。

　所以現在我們剩下的任務就是“枚舉矩陣寬度” 來達到? “枚舉寬度為up-down的所有子矩陣，找出寬度為up-down的最大子矩陣”。

　我們寬度已知，所有要枚舉也就是長度，這樣我們可以把 “矩陣壓縮稱為一條線”。

　這時候線段樹的功能就能解決這個問題了。

　用線段樹來維護最大字段和，其實維護的是 “寬度為up-down”的最大矩陣和。

　這樣我們的時間復雜度就可以達到O(n^2 logn)了。

　記得每次改變下界的時候要初始化線段樹，關于這個初始化代碼中還有一個小技巧，差不多減少了1.5s左右的時間。

?

?

#include <bits/stdc++.h>using namespace std; typedef double dou; typedef long long ll; typedef pair<int, int> pii; typedef map<int, int> mii;#define pai acos(-1.0) #define M 4005 #define inf 0x3f3f3f3f #define mod 1000000007 #define IN inline #define left k<<1 #define right k<<1|1 #define lson L, mid, left #define rson mid + 1, R, right #define W(a) while(a) #define lowbit(a) a&(-a) #define ms(a,b) memset(a,b,sizeof(a)) #define Abs(a) (a ^ (a >> 31)) - (a >> 31) #define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)int T, n; ll vx[M], vy[M]; ll xlen, ylen, pos, ans; struct Data {int x, y, val;bool operator <(Data& t) {return y < t.y;} }node[M]; struct Data_t {ll sum;ll Lmax, Rmax, Max; }tree[M << 2];IN void Updata(int L, int R, int k, int id,int add) {if (L == R) {tree[k].sum += (ll)add;tree[k].Lmax = tree[k].Rmax = tree[k].Max = tree[k].sum;return;}int mid = L + R >> 1;if (id <= mid)Updata(lson, id, add);else Updata(rson, id, add);//維護最大字段和tree[k].sum = tree[left].sum + tree[right].sum;tree[k].Lmax = max(tree[left].Lmax, tree[left].sum + tree[right].Lmax);tree[k].Rmax = max(tree[right].Rmax, tree[right].sum + tree[left].Rmax);tree[k].Max = max(max(tree[left].Max, tree[right].Max), tree[left].Rmax + tree[right].Lmax); }int main() {false_stdio;cin >> T;W(T--) {cin >> n;for (int i = 1; i <= n; i++) {cin >> node[i].x >> node[i].y >> node[i].val;vx[i] = node[i].x, vy[i] = node[i].y;}//二維坐標離散化sort(vx + 1, vx + n + 1);sort(vy + 1, vy + n + 1);xlen = unique(vx + 1, vx + n + 1) - vx - 1;ylen = unique(vy + 1, vy + n + 1) - vy - 1;for (int i = 1; i <= n; i++) {node[i].x = lower_bound(vx + 1, vx + xlen + 1, node[i].x) - vx;node[i].y = lower_bound(vy + 1, vy + ylen + 1, node[i].y) - vy;}sort(node + 1, node + n + 1);ans = 0;//首先枚舉下界for (int dw = 1; dw <= ylen; dw++) {pos = 1;memset(tree, 0, (xlen * 4 + 5) * sizeof(Data_t));//初始化線段樹，離散化完有多少個點就初始化多大 W(node[pos].y < dw && pos <= n)pos++;//直接跳過小于下界的點for (int up = dw; up <= ylen; up++) {//枚舉上界W(pos <= n && node[pos].y <= up) {//將上界與下屆之間的點加入線段樹中Updata(1, xlen, 1, node[pos].x, node[pos].val);pos++;}ans = max(ans, tree[1].Max);}}cout << ans << endl;}return 0; }

?

轉載于:https://www.cnblogs.com/caibingxu/p/11364440.html

總結

以上是生活随笔為你收集整理的2019杭电暑假多校训练 第六场 Snowy Smile HDU - 6638的全部內容，希望文章能夠幫你解決所遇到的問題。

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