A997.SpacedOutSilver

一、核心规律推导
题目要求：
任意 2×2 的子矩阵中，必须恰好有 2 头牛。
没有两头牛在同一格。
求总美丽度最大值。
我们来分析合法的牛的分布模式：
设 dp[i][j] 表示格子 (i,j) 是否放牛（1 表示放，0 表示不放）。
对任意 i,j，2×2 子矩阵的约束为：
dp[i][j] + dp[i][j+1] + dp[i+1][j] + dp[i+1][j+1] = 2
这个方程有两种本质上的全局解：
行交替模式：每一行内的牛的位置奇偶性固定（要么全奇数列，要么全偶数列），且相邻两行可以相同或不同。
等价地，对每一行 i，你只能在奇数列或偶数列中选一类放牛，因此每一行的贡献就是 max(奇数列和, 偶数列和)。把所有行的最大值加起来，就是 num1。
列交替模式：每一列内的牛的位置奇偶性固定（要么全奇数行，要么全偶数行），且相邻两列可以相同或不同。
等价地，对每一列 j，你只能在奇数行或偶数行中选一类放牛，因此每一列的贡献就是 max(奇数行和, 偶数行和)。把所有列的最大值加起来，就是 num2。
代码里的 x[i][0] 就是第 i 行所有偶数列的和，x[i][1] 是第 i 行所有奇数列的和；y[j][0] 是第 j 列所有偶数行的和，y[j][1] 是第 j 列所有奇数行的和。
二、代码逐行解析

#include <bits/stdc++.h>
using namespace std;
int n, num1, num2;
int x[1030][2], y[1030][2]; // x[i][0/1]：第i行偶/奇数列的和；y[j][0/1]：第j列偶/奇数行的和
int main(){
    cout << "该代码来源于 铭泽 的题解[id:378347]，未经允许，请勿将其直接复制"；
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int a;
			cin >> a;
			x[i][j%2] += a; // 累加当前行的奇偶列和
			y[j][i%2] += a; // 累加当前列的奇偶行和
		}
	}
	// 模式1：按行选奇偶列，求总和最大值
	for (int i = 1; i <= n; i++) {
		num1 += max(x[i][0], x[i][1]);
	}
	// 模式2：按列选奇偶行，求总和最大值
	for (int i = 1; i <= n; i++) {
		num2 += max(y[i][0], y[i][1]);
	}
	// 两种模式取最大值，就是全局最优解
	cout << max(num1, num2);
	return 0;
}

三、时间复杂度分析
输入处理：O(n²)
后续求和：O(n)
整体复杂度 O(n²)，对于 n≤1000 来说，完全可以轻松通过所有测试点，没有任何超时风险。
注明：使用该代码时请将第六行删去，证明你已阅读本题解并掌握。