C. Portal（二维前缀和 + 枚举的优化）

Codeforces Round #745 (Div. 2)

给出一个 n × m n times m n×m的矩阵，找出一个经过最少次数的修改操作之后满足以下条件的子矩阵 a × b a times b a×b。输出最小的操作次数。

• a ≥ 5 , b ≥ 4 ge 5, b ge 4 ≥5,b≥4
• 四个边界要求全部是1，四个角除外（四个角可以是1，也可以是0）
• 中间部分要求全部都是0
  quad
  每次操作可以将一个0变成1，也可以将一个1变成0

qquad We can enumerate the two corner of the submatrix, calculate the answer by precalculating the prefix sums. The time complexity is O( ∑ n m ∑nm ∑nm). When we enumerated the upper edge and the lower edge of the submatrix, we can calculate the answer by prefix sum. Assume the left edge of the submatrix is l, and the right edge is r. The part of anwer contributed by upper and lower edge are two segments, we can calculate the answer by prefix sums. The middle empty part is a submaxtrix, and we can use prefix sums too. Since we have enumerated the upper edge and lower edge, the left edge part is just about l, and the right part is just about r. Then we enumerate l, the answer of the best r can be calculated by precalculating the suffix miniums. The time complexity is O ( ∑ n 2 m ) O(∑n^2m) O(∑n2m), space complexity is O ( n m ) O(nm) O(nm).

算法主要思想：

1. 可以先用二维前缀和预处理一下矩阵，然后枚举矩阵的上边界和下边界。假设左边界为l，右边界为r。
2. 先固定左边界l = 1，枚举右边界，求出对应的操作次数。
3. 在左边界相同的情况下，右边界更大的反而操作次数更少的，则应取代较小的边界边界的情况。（ 将 O ( n 4 ) 优 化 到 O ( n 3 ) 将O(n^4)优化到O(n^3) 将O(n4)优化到O(n3)）
4. 然后枚举左边界，求出总的操作次数。

考虑到枚举左边界时方便计算结果，在枚举左边界和右边界时稍微做了一点变化。可以看代码中的注释：

char s[402];
int sum[401][401], f[401];
inline int GetSum(int lx, int ly, int rx, int ry) {
	return sum[rx][ry] - sum[rx][ly - 1] - sum[lx - 1][ry] + sum[lx - 1][ly - 1];
}
inline void Solve() {
	int n, m, i, j, k, ans = 999999, cur;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%s", s + 1);
		for (j = 1; j <= m; j++) {
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[j] == '1');
		}
	}
	for (i = 1; i != n; i++) {
		for (j = i + 4; j <= n; j++)
		{
			for (k = 4; k <= m; k++) 
			{
				f[k] = GetSum(i + 1, 1, j - 1, k - 1) - GetSum(i, 1, i, k - 1) - GetSum(j, 1, j, k - 1) - GetSum(i + 1, k, j - 1, k) + (k << 1) + j - i - 3;
			  //f[k] = GetSum(i + 1, 1, j - 1, k - 1) +
			  //      (k - 1) * 2 - GetSum(i, 1, i, k - 1) - GetSum(j, 1, j, k - 1) + 
			  //	   j - i - 1 - GetSum(i + 1, k, j - 1, k);
			  //此处将左边界归属于中间部分，左上角归属于顶部，左下角归属于底部。方便枚举左边界时，减去左边界左边部分。
			}
			for (k = m - 1; k >= 4; k--) //预处理右边界。若在左边界相同的情况下，右边界更大的反而更优，则应取代当前边界的情况。
			{							 //用大边界的取代小边界的结果并不影响左边界的枚举。
				f[k] = min(f[k + 1], f[k]);
			}
			for (k = 1; k <= m - 3; k++)
			{							
				cur = f[k + 3] - GetSum(i + 1, 1, j - 1, k) + GetSum(i, 1, i, k) + GetSum(j, 1, j, k) - (k << 1) - GetSum(i + 1, k, j - 1, k) + j - i - 1;
			  //cur = f[k + 3] - 
			  //      GetSum(i + 1, 1, j - 1, k) - (k * 2 - GetSum(i, 1, i, k) - GetSum(j, 1, j, k)) +
			  //      j - i - 1 - GetSum(i + 1, k, j - 1, k);
				ans = min(cur, ans);
			}
		}
	}
	printf("%dn", ans);
}
int main() {
	int t;
	scanf("%d", &t);
	while (t != 0) {
		Solve();
		t--;
	}
	return 0;
}