UVa 10827 - Maximum Sum on a Torus

链接

传送门

题意

给出一个$n \times n (1 \leq n \leq 75)$的矩阵,矩阵可以滚动,求最大的连续子矩阵的和。

思路

将矩阵扩展为$2n \times 2n$的矩阵,枚举行的起点和终点,求出每一列的和的前缀和,然后用前缀和求最大连续和,但是由于有最长不能超过$n$的限制,使用单调队列计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 160;
int a[maxn][maxn];
int s[maxn], ss[maxn], n, n2;
deque<int> q;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, ans = -100;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%d", &a[i][j]);
a[i + n][j] = a[i][j + n] = a[i + n][j + n] = a[i][j];
if (a[i][j] > ans) {
ans = a[i][j];
}
}
}
int n2 = n << 1;
if (ans > 0) {
for (int i = 1; i <= n; ++i) {
memset(s, 0, sizeof s);
for (int j = i; j < i + n; ++j) {
for (int k = 1; k <= n2; ++k) {
s[k] += a[j][k];
ss[k] = s[k] + ss[k - 1];
}
q.clear();
for(int k = 1; k <= n2; ++k) {
while(!q.empty() && ss[q.back()] > ss[k]) {
q.pop_back();
}
q.push_back(k);
while(k - q.front() > n) {
q.pop_front();
}
int val = ss[k] - ss[q.front()];
if(val > ans) {
ans = val;
}
}
}
}
}
printf("%d\n", ans);
}
return 0;
}