链接
传送门
题意
给出一个\(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;
}
|