[UVA] 10827 - Maximum sum on a torus
Problem H
Maximum sum on a torus
Input: Standard Input
Output: Standard Output
A grid that wraps both horizontally and vertically is called a torus. Given a torus where each cell contains an integer, determine the sub-rectangle with the largest sum. The sum of a sub-rectangle is the sum of all the elements in that rectangle. The grid below shows a torus where the maximum sub-rectangle has been shaded.
|
1 |
-1 |
0 |
0 |
-4 |
|
2 |
3 |
-2 |
-3 |
2 |
|
4 |
1 |
-1 |
5 |
0 |
|
3 |
-2 |
1 |
-3 |
2 |
|
-3 |
2 |
4 |
1 |
-4 |
Input
The first line in the input contains the number of test cases (at most 18). Each case starts with an integer N (1≤N≤75) specifying the size of the torus (always square). Then follows N lines describing the torus, each line containing N integers between -100 and 100, inclusive.
Output
For each test case, output a line containing a single integer: the maximum sum of a sub-rectangle within the torus.
Sample Input Output for Sample Input
251 -1 0 0 -42 3 -2 -3 24 1 -1 5 03 -2 1 -3 2-3 2 4 1 -431 2 34 5 67 8 9 |
15
45 |
做法 : DP (最大矩形的變形)
最原始的最大矩形是 O(N^3) 沒有限制子矩形的長寬大小,
而在此題會有限制, 因此需要一個 O(N) 的檢查, 因此是 O(N^4)
#include <stdio.h>
#include <string.h>
int main() {
int T, N;
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
int A[300][300];
int i, j, k, l;
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++) {
scanf("%d", &A[i][j]);
A[i+N][j] = A[i][j+N] = A[i+N][j+N] = A[i][j];
}
}
int length, width, max = 0, tmp;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
max = max > A[i][j] ? max : A[i][j];
int tmpN = N << 1;
int sum[300] = {}, tmpSum, tmplength, tmpMax;
if(max != 0) {
for(i = 0; i < N; i++) {
memset(sum, 0, sizeof(sum));
for(j = i; j < tmpN; j++) {
if(j-i+1 > N) break;
length = 0, tmp = 0;
for(k = 0; k < tmpN; k++) {
sum[k] += A[j][k];
length++;
tmp += sum[k];
if(length > N) {
tmp -= sum[k-length+1];
length--;
}
tmpSum = 0, tmplength = length, tmpMax = tmp;
for(l = k-length+1; l <= k; l++) {
tmpSum += sum[l];
if(tmp-tmpSum >= tmpMax)
tmplength = k-l, tmpMax = tmp-tmpSum;
}
tmp = tmpMax, length = tmplength;
if(length > 0) {
if(tmp > max)
max = tmp;
if(k-length+1 >= N) break;
}
}
for(k++; k < tmpN; k++) sum[k] += A[j][k];
}
}
}
printf("%d\n", max);
}
return 0;
}
應該可以壓一個 N 。
對於固定一組 i, j 所算出來的 sum[k] 來說，如果能夠在 [0, N-1] 找到連續區間的 minimum sum ，那麼就可以反過來求出跨過左右端的區間的 maximum sum 了。