[COCI2021-2022#6] Zemljište

[COCI2021-2022#6] Zemljište

题意

给出一个矩阵，一个子矩阵的权值为 \(|m-a|+|m-b|\)，\(m\) 为子矩阵数值和，\(a,b\) 为给出的数。

求该矩阵权值最小的子矩阵。

思路

枚举子矩阵上界和下界，左右界使用双指针枚举，令 \(a<b\)。

对于每个左界，不断扩展右界直到子矩阵和大于 \(b\)，因为再往右扩展一定不优。

每次扩展时统计答案即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505 + 5;
int r, s, a, b, ans = 1e9;
int v[N][N], sum[N][N];
int val(int x_1, int y_1, int x_2, int y_2) {
	return sum[x_2][y_2] - sum[x_1 - 1][y_2] - sum[x_2][y_1 - 1] + sum[x_1 - 1][y_1 - 1];
}
int calc(int x_1, int y_1, int x_2, int y_2) {
	return abs(a - val(x_1, y_1, x_2, y_2)) + abs(b - val(x_1, y_1, x_2, y_2));
}
void solve() {
	cin >> r >> s >> a >> b;
	if (a > b) swap(a, b);
	for (int i = 1; i <= r; i ++)
		for (int j = 1; j <= s; j ++)
			cin >> v[i][j];
	for (int i = 1; i <= r; i ++)
		for (int j = 1; j <= s; j ++)
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + v[i][j] - sum[i - 1][j - 1];
	for (int i = 1; i <= r; i ++) {
		for (int j = i; j <= r; j ++) {
			for (int L = 1, R = 1; L <= s; L ++) {
				R = max(L, R);
				while (R < s && val(i, L, j, R) <= b) 
					ans = min(ans, calc(i, L, j, R)), R ++;
				ans = min(ans, calc(i, L, j, R));
			}
		}
	}
	cout << ans << "\n";
} 
signed main() {
	int T = 1;
//	cin >> T;
	while (T --)
		solve();
	return 0;
}