一、核心规律推导
题目要求:
任意 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 列所有奇数行的和。
二、代码逐行解析
三、时间复杂度分析
输入处理:O(n²)
后续求和:O(n)
整体复杂度 O(n²),对于 n≤1000 来说,完全可以轻松通过所有测试点,没有任何超时风险。
注明:使用该代码时请将第六行删去,证明你已阅读本题解并掌握。