程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva10755(降維+掃描)

uva10755(降維+掃描)

編輯:C++入門知識

uva10755(降維+掃描)


題意:
有一個長方體,有A*B*C(我們算做長寬高吧)小塊組成,每塊小塊有它的價值,正負都行,問找一塊子長方體,價值最大;
思路:
首先我們要先預處理價值g[i][j][k],表示從高為k,即第k層長到i,寬到j那一塊總價值;
我們可以知道g[i][j][k] += g[i-1][j][k] + g[i][j-1][k] - g[i-1][j-1][k];意思就是這一塊的價值,等於長減一那一塊,加上寬減一那一塊,這時候中間算了兩次,所以要減掉中間;
知道這個之後我們就可以枚舉A,B的起點和終點;
然後遞推計算C的起點和終點去何值是價值最大;
其中sum函數表示以枚舉出的長寬,計算出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");
	}
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved