ZOJ 1074 To the Max(DP 최대 하위 매트릭스 및)
5832 단어 max
Time Limit: 2 Seconds
Memory Limit: 65536 KB
ProblemGiven a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.As an example, the maximal sub-rectangle of the array:0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2is in the lower left corner:9 2-4 1-1 8and has a sum of 15.The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
Output
Output the sum of the maximal sub-rectangle.
Input40 -2 -7 0 9 2 -6 2-4 1 -4 1 -18 0 -2Output15
코드는 다음과 같습니다.
1 # include<stdio.h>
2 # include<string.h>
3 # define N 101
4 int main(){
5 int a[N][N],b[N];
6 int n,i,j,k;
7 while(scanf("%d",&n)!=EOF)
8 {
9 for(i=0;i<n;i++)
10 for(j=0;j<n;j++)
11 scanf("%d",&a[i][j]);
12 int max= -12345;
13 for(i=0;i<n;i++) // i j
14 {
15 memset(b,0,sizeof(b));
16 for(j=i;j<n;j++)
17 {
18 int sum=0;
19 for(k=0;k<n;k++)
20 {
21 b[k] += a[j][k];
22 sum += b[k];
23 if(sum<0) sum=b[k];
24 if(sum>max) max=sum;
25 }
26 }
27 }
28 printf("%d
",max);
29 }
30 return 0;
31 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
🏃♀️[프로그래머스] 징검다리 건너기문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.