uva10755(降維＋掃描)

uva10755(降維＋掃描)

題意：
有一個長方體，有Ａ＊Ｂ＊Ｃ（我們算做長寬高吧）小塊組成，每塊小塊有它的價值，正負都行，問找一塊子長方體，價值最大；
思路：
首先我們要先預處理價值g[i][j][k],表示從高為k,即第k層長到ｉ，寬到ｊ那一塊總價值；
我們可以知道g[i][j][k] += g[i-1][j][k] + g[i][j-1][k] - g[i-1][j-1][k];意思就是這一塊的價值，等於長減一那一塊，加上寬減一那一塊，這時候中間算了兩次，所以要減掉中間；
知道這個之後我們就可以枚舉Ａ，Ｂ的起點和終點；
然後遞推計算Ｃ的起點和終點去何值是價值最大；
其中ｓｕｍ函數表示以枚舉出的長寬，計算出endC這一層的價值，在endC++,計算下一層，疊加；如果疊加後的結果是負的，那麼就要從startC那一層開始，一層層往下減，知道變為正的，或者全部都減掉位置（這裡和最大連續和是一樣的）；
這樣我們就把三維化為二維，知道每一層的價值，去算最大連續和：

#include
#include
#include
#define ll long long
using namespace std;

const ll INF = (ll)1 << 60;
const int N = 25;
ll g[N][N][N];
int a,b,c;

ll sum(int startA, int endA, int startB, int endB, int C) {
	return g[endA][endB][C] - g[startA - 1][endB][C] - g[endA][startB - 1][C] + g[startA - 1][startB - 1][C];
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		memset(g, 0 , sizeof(g));
		scanf("%d%d%d",&a,&b,&c);
		for(int i = 1 ; i <= a ;i++) {
			for(int j = 1; j <= b ; j++) {
				for(int k = 1 ; k <= c ;k++) {
					scanf("%lld",&g[i][j][k]);
					g[i][j][k] += (g[i - 1][j][k] + g[i][j - 1][k] - g[i - 1][j - 1][k]);
				}
			}
		}
		ll ans = -INF;
		for(int startA = 1 ; startA <= a ; startA++) {
			for(int endA = startA ; endA <= a ;endA++) {
				for(int startB = 1; startB <= b; startB++) {
					for(int endB = startB  ; endB <= b; endB++) {
						int startC = 1;
						int endC = 1;
						ll m = 0;
						while(endC <= c) {
							m += sum(startA, endA, startB, endB, endC);
							if(m > ans)
								ans = m;
							while(m < 0 && startC <= endC) {
								m -= sum(startA, endA, startB, endB, startC);
								startC++;
								if(startC <= endC && m > ans)
									ans = m;
							}
							endC++;
						}
					}
				}
			}
		}
		printf("%lld\n",ans);
		if(t)
			printf("\n");
	}
}