Spaced Out (USACO Silver 2021 January)

用暴力搜索所有状态（每个2x2方格有6种选择），或者DP的办法（按行按列DP，状态都比较多），这时会发现复杂度都太高。所以我们需要找规律。

观察之后我们声明: 一定有一个方向（行或者列）上，牛是交替出现的。为什么这么说呢？我们分析可能的情况：

一旦有相邻两个牛（例如下面左上角的两头牛），就会形成所有行（或者所有列）内牛都交替出现的模式：

  C . C . C
  C . C . C
  . C . C .
  C . C . C

剩下情况，就是完全没有相邻的牛，那这种情况下，牛在两个方向上都是交替出现的。

  C . C
  . C .
  C . c

所以可以从行交替，列交替两个方向来求最优。办法就是直接greedy，因为每行或每列是独立选择的，选最优就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[1005][1005];
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    int ans1 = 0, ans2 = 0;    // ans1: 同一行内牛交替的解，ans2：同一列内牛交替的解
    for (int i = 0; i < n; i++) {
        int even1 = 0, total1 = 0;
        int even2 = 0, total2 = 0;
        for (int j = 0; j < n; j++) {
            if (j % 2 == 0) {
                even1 += a[i][j];
                even2 += a[j][i];
            }
            total1 += a[i][j];
            total2 += a[j][i];
        }
        ans1 += max(even1, total1 - even1);
        ans2 += max(even2, total2 - even2);
    }
    printf("%d\n", max(ans1, ans2));
    return 0;
}