「ACM 算法实践」[解题报告]麦田-526互联

分析

首先，前缀和的思路是很显然的。然后我们很容易想到暴力枚举矩形的左上角和右下角，然而 \(\mathcal{O}(n^4)\) 的算法过不去，哪怕把最后一维用二分，倒数第二维加一点剪枝也还是会 T 两个点。

这时候应该考虑将多行/列压缩为一行/列，然后再使用双指针枚举列/行。详细来说就是将 \(i\) 行到 \(j\) 行压缩为 \(1\) 行，然后双指针枚举 \(l\) 到 \(r\) 列，判定是否满足条件。

状态压缩其实是在像矩形这种多维情况下常用的一种方法，虽然我之前也有考虑过，但是没有想到用双指针，看了题解之后恍然大悟，到了写代码的阶段却又发现自己连双指针都不会写。。。

唉，太久没写代码了，寒假不应该狠狠摆烂的。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int gi() {
	int x = 0, f = 1; char c = getchar();
	for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return x * f;
}

const int N = 505;

ll ans;
int n, m, mx;
int s[N][N];

int cal(int i, int j, int k, int l) {
	return s[i][j] - s[i][l - 1] - s[k - 1][j] + s[k - 1][l - 1];
}

int main() {
	n = gi(), m = gi(), mx = gi();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			s[i][j] = gi();
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	for (int i = 1; i <= m; ++i)
		for (int j = i; j <= m; ++j) {
			int l = 1, r = 1;
			while (r <= n) {
				while (l <= r && cal(r, j, l, i) > mx) l++;
				if (l <= r) ans += r - l + 1;
				r++;
			}
		}
	printf("%lld", ans);
	return 0;
}