FOJ 1018 Maximal Sum(三维子矩最大和)

Problem Description

Given a cube of positive and negative integers, find the sub-cube with the largest sum. The sum of a cube is the sum of all the elements in that cube. In this problem, the sub-cube with the largest sum is referred to as the maximal sub-cube.

A sub-cube is any contiguous sub-array of size 1 x 1 x 1 or greater located within the whole array.

As an example, if a cube is formed by following 3 x 3 x 3 integers:

0 -1 3 -5 7 4 -8 9 1 -1 -3 -1 2 -1 5 0 -1 3 3 1 -1 1 3 2 1 -2 1

Then its maximal sub-cube which has sum 31 is as follows:

7 4 9 1 -1 5 -1 3 3 2 -2 1

Input

Each input set consists of two parts. The first line of the input set is a single positive integer N between 1 and 20, followed by N x N x N integers separated by white-spaces (newlines or spaces). These integers make up the array in a plane, row-major order (i.e., all numbers on the first plane, first row, left-to-right, then the first plane, second row, left-to-right, etc.). The numbers in the array will be in the range [-127,127].

The input is terminated by a value 0 for N.

Output

The output is the sum of the maximal sub-cube.

Sample Input

3 0 -1 3 -5 7 4 -8 9 1 -1 -3 -1 2 -1 5 0 -1 3 3 1 -1 1 3 2 1 -2 1 0

Sample Output

31

 

本题是三维的，建议先从一维做起，http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=44

二维 的：http://poj.org/problem?id=1050

直接贴代码，很简单的题

 

AC代码：  

 

# include <stdio.h> # include <string.h> # include <limits.h> # include <algorithm> using namespace std; int a[30][30][30]; int s[30][30][30], area[30][30][30]; int dp[30]; int main(){ int i, j, k, l, m, n, d, g_max, l_max; while(scanf("%d", &n)){ if(n==0){ break; } g_max=INT_MIN; memset(s, 0, sizeof(s)); for(i=1; i<=n; i++){ for(j=1; j<=n; j++){ for(k=1; k<=n; k++){ scanf("%d", &a[i][j][k]); s[i][k][j]=s[i][k][j-1]+a[i][j][k]; } } } for(k=1; k<=n; k++){ for(l=k; l<=n; l++){ for(m=1; m<=n; m++){ memset(area, 0, sizeof(area)); for(j=m; j<=n; j++){ l_max=INT_MIN; for(i=1; i<=n; i++){ area[i][m][j]=area[i][m][j-1]+s[i][j][l]-s[i][j][k-1]; } dp[0]=0; for(i=1; i<=n; i++){ dp[i]=max(area[i][m][j], dp[i-1]+area[i][m][j]); if(dp[i]>l_max){ l_max=dp[i]; } } if(l_max>g_max){ g_max=l_max; } } } } } printf("%d\n", g_max); } return 0; }