本文共 4107 字，大约阅读时间需要 13 分钟。
题意：
求一个子矩阵要求其矩阵内的合最大。
题解：
正常的求最大子矩阵的复杂度是O(n^3)
对于这一题说复杂度过不去，注意到这个题总共只有2000个点关键点在与这里优化
最大子矩阵可以压缩矩阵变成最大字段和问题
然后可以通过带修改的最大字段和维护这2000个点，复杂度就变成了了O(n^2logn)
将算出每一列的合的操作 用待修改的最大字段和的线段树维护。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define pi acos(-1.0) 13 #define eps 1e-9 14 #define fi first 15 #define se second 16 #define rtl rt<<1 17 #define rtr rt<<1|1 18 #define bug printf("******\n") 19 #define mem(a,b) memset(a,b,sizeof(a)) 20 #define name2str(x) #x 21 #define fuck(x) cout<<#x" = "< < = b; i--) 30 #define FRL(i,a,b) for(i = a; i < b; i++)+ 31 #define FRLL(i,a,b) for(i = a; i > b; i--) 32 #define FIN freopen("data.txt","r",stdin) 33 #define gcd(a,b) __gcd(a,b) 34 #define lowbit(x) x&-x 35 #define rep(i,a,b) for(int i=a;i =b;--i) 37 using namespace std; 38 typedef long long LL; 39 typedef unsigned long long ULL; 40 const int maxn = 4000 + 7; 41 const int maxm = 8e6 + 10; 42 const int mod = 1e9 + 7; 43 const int INF = 0x3f3f3f3f; 44 int T, n; 45 LL s[maxn], x[maxn], y[maxn], a[maxn], b[maxn], w[maxn], mp[maxn][maxn]; 46 struct Segtree { 47 LL maxx, vl, vr, sum, fg; 48 49 } Tree[maxn << 3]; 50 void updata ( int rt ) { 51 Tree[rt].maxx = max ( Tree[rtl].maxx, max ( Tree[rtr].maxx, Tree[rtl].vr + Tree[rtr].vl ) ); 52 Tree[rt].sum = Tree[rtl].sum + Tree[rtr].sum; 53 Tree[rt].vl = max ( Tree[rtl].vl, Tree[rtl].sum + Tree[rtr].vl ); 54 Tree[rt].vr = max ( Tree[rtr].vr, Tree[rtr].sum + Tree[rtl].vr ); 55 } 56 void build ( int l, int r, int rt ) { 57 Tree[rt].fg = true; 58 if ( l == r ) { 59 Tree[rt].sum = s[l]; 60 Tree[rt].maxx = s[l]; 61 Tree[rt].vl = s[l]; 62 Tree[rt].vr = s[l]; 63 return ; 64 } 65 int mid = ( l + r ) >> 1; 66 build ( l, mid, rtl ); 67 build ( mid + 1, r, rtr ); 68 updata ( rt ); 69 } 70 void add ( int l, int r, int rt, int pos, int to ) { 71 if ( l > pos || r < pos ) return ; 72 if ( l == r ) { 73 Tree[rt].sum += to; 74 Tree[rt].maxx += to; 75 Tree[rt].vl += to; 76 Tree[rt].vr += to; 77 return ; 78 } 79 int mid = ( l + r ) >> 1; 80 add ( l, mid, rtl, pos, to ); 81 add ( mid + 1, r, rtr, pos, to ); 82 updata ( rt ); 83 } 84 Segtree query ( int l, int r, int rt, int sa, int se ) { 85 if ( sa <= l && r <= se ) return Tree[rt]; 86 int mid = ( l + r ) >> 1; 87 if ( sa > mid ) return query ( mid + 1, r, rtr, sa, se ); 88 if ( se <= mid ) return query ( l, mid, rtl, sa, se ); 89 Segtree t, lson, rson; 90 lson = query ( l, mid, rtl, sa, se ); 91 rson = query ( mid + 1, r, rtr, sa, se ); 92 t.vl = max ( lson.vl, lson.sum + rson.vl ); 93 t.vr = max ( rson.vr, lson.vr + rson.sum ); 94 t.maxx = max ( lson.vr + rson.vl, max ( lson.maxx, rson.maxx ) ); 95 return t; 96 } 97 vector v[maxn]; 98 int main() { 99 // FIN;100 sf ( T );101 while ( T-- ) {102 sf ( n );103 for ( int i = 1 ; i <= n ; i++ ) {104 scanf ( "%lld%lld%lld", &x[i], &y[i], &w[i] );105 a[i] = x[i], b[i] = y[i];106 v[i].clear();107 }108 sort ( a + 1, a + 1 + n ), sort ( b + 1, b + 1 + n );109 int len1 = unique ( a + 1, a + 1 + n ) - a - 1;110 int len2 = unique ( b + 1, b + 1 + n ) - b - 1;111 for ( int i = 0 ; i <= n ; i++ ) for ( int j = 0 ; j <= n ; j++ ) mp[i][j] = 0;112 for ( int i = 1 ; i <= n ; i++ ) {113 x[i] = lower_bound ( a + 1, a + 1 + len1, x[i] ) - a;114 y[i] = lower_bound ( b + 1, b + 1 + len2, y[i] ) - b;115 mp[y[i]][x[i]] += w[i];116 }117 for ( int i = 1 ; i <= n ; i++ )118 for ( int j = 1 ; j <= n ; j++ )119 if ( mp[i][j] ) v[i].push_back ( j );120 LL ans = 0;121 for ( int i = 1 ; i <= n ; i++ ) {122 for ( int j = 1 ; j <= n ; j++ ) s[j] = mp[i][j];123 build ( 1, n, 1 );124 ans = max ( ans, query ( 1, n, 1, 1, n ).maxx );125 for ( int j = i + 1 ; j <= n ; j++ ) {126 for ( int k = 0 ; k < v[j].size() ; k++ ) {127 add ( 1, n, 1, v[j][k], mp[j][v[j][k]] );128 }129 ans = max ( ans, query ( 1, n, 1, 1, n ).maxx );130 }131 }132 printf ( "%lld\n", ans );133 }134 return 0;135 }
转载于:https://www.cnblogs.com/qldabiaoge/p/11318738.html
