本文主要是介绍【UVa】10755 Garbage Heap 三维前缀和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目分析：将前缀和应用到三维，求最大子矩阵。为S[x][y][z]数组中每个坐标保存从(0,0,0)到(x,y,z)范围内的子矩阵的元素和，最后用多次区间加减法可以得到需要的子矩阵的元素和，再用类似一维求最大连续和的方法求三维最大连续和。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define SIZE MAXN][MAXN][MAXN
#define FFF FOR ( x , 1 , A ) FOR ( y , 1 , B ) FOR ( z , 1 , C )typedef long long LL ;const int MAXN = 21 ;
const LL INF = 1e18 ;LL S[SIZE] ;
int A , B , C ;LL calculate ( int x1 , int x2 , int y1 , int y2 , int z1 , int z2 ) {LL res = 0 ;res += S[x2 ][y2 ][z2 ] ;res -= S[x1 - 1][y2 ][z2 ] ;res -= S[x2 ][y1 - 1][z2 ] ;res -= S[x2 ][y2 ][z1 - 1] ;res += S[x1 - 1][y2 ][z1 - 1] ;res += S[x2 ][y1 - 1][z1 - 1] ;res += S[x1 - 1][y1 - 1][z2 ] ;res -= S[x1 - 1][y1 - 1][z1 - 1] ;return res ;
}void solve () {scanf ( "%d%d%d" , &A , &B , &C ) ;CLR ( S , 0 ) ;FFF scanf ( "%lld" , &S[x][y][z] ) ;FFF S[x][y][z] += S[x - 1][y][z] ;FFF S[x][y][z] += S[x][y - 1][z] ;FFF S[x][y][z] += S[x][y][z - 1] ;//FFF printf ( "S[%d][%d][%d] = %lld\n" , x , y , z , S[x][y][z] ) ;LL ans = -INF ;FOR ( x1 , 1 , A )FOR ( x2 , x1 , A )FOR ( y1 , 1 , B )FOR ( y2 , y1 , B ) {LL M = 0 ;FOR ( z , 1 , C ) {LL sum = calculate ( x1 , x2 , y1 , y2 , 1 , z ) ;ans = max ( ans , sum - M ) ;M = min ( M , sum ) ;}}printf ( "%lld\n" , ans ) ;
}int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- ) {solve () ;if ( T )putchar ( '\n' ) ;}return 0 ;
}这篇关于【UVa】10755 Garbage Heap 三维前缀和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
