AcWing 4405. 统计子矩阵(暴搜+优化)
原题链接
中等
作者:
fourth_nt
,
2024-04-10 17:47:17
,
所有人可见
,
阅读 1
暴搜
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long k = sc.nextLong();
long[][] s = new long[n + 1][m + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + sc.nextInt();
}
}
long res = 0;
//暴搜
for(int x1 = 1; x1 <= n; x1++) {
for(int y1 = 1; y1 <= m; y1++) {
for(int x2 = x1; x2 <= n; x2++) {
for(int y2 = y1; y2 <= m; y2++) {
long t = s[x2][y2] - s[x2 - x1][y2] - s[x2][y2 - y1] + s[x2 - x1][y2 - y1];
if(t <= k)
res++;
}
}
}
}
System.out.print(res);
}
}
优化
import java.util.Scanner;
public class Main {
static long[][] s;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long k = sc.nextLong();
s = new long[n + 1][m + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + sc.nextInt();
}
}
long res = 0;
//枚举上下边界
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
//用左右边界来维护从而优化掉一层循环
for(int l = 1, r = 1; r <= m; r++) {
while(l <= r && Cal(i, l, j, r) > k) {
l++;
}
if(l <= r)
res += r - l + 1;
}
}
}
System.out.print(res);
}
public static long Cal(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
}