解法：DP & 分类讨论
本题难点在于讨论清楚各种情况。
容易想到设计状态 $f(j, i)$ 表示只考虑前 $j$ 列，且第 $j$ 列涂黑了前 $i$ 行的最大得分。首先注意到不会出现连续三列都不操作的情况，因为这样会导致中间的一列不参与计分，此时可以把中间的一列全涂黑，答案不会变差。因此我们只需要考虑上一个操作的列是 $(j - 1)$，$(j - 2)$ 还是 $(j - 3)$ 的情况。
以下转移方程中，$s(j, i_l, i_r)$ 表示第 $j$ 列第 $i_l$ 行到第 $i_r$ 行的分数之和。
情况 1：当上一个操作的列是 $(j - 1)$，且它涂黑了 $i'$ 行时
情况 1.1：若 $i' \le i$，需要考虑第 $(j - 1)$ 列涂黑的格子数比 $(j - 2)$ 列多还是少。注意到最优答案下，第 $(j - 1)$ 列涂黑的格子一定比 $(j - 2)$ 列多，否则在两边涂黑的格子都比中间多的情况下，中间列的操作只是在失去分数，不优。
这种情况下，本次操作将损失第 $j$ 列前 $i'$ 行的分数，但获得了第 $(j - 1)$ 列第 $(i' + 1)$ 行到第 $i$ 的分数，以及第 $(j + 1)$ 列前 $i$ 行的分数。
另外，为了维护这一列和上一列黑格子的数量关系，我们需要在 DP 状态里加一维，变成 $f(j, i, t = 0/1)$，表示只考虑前 $j$ 列，且第 $j$ 列涂黑了前 $i$ 行，且第 $j$ 列涂黑的格子数比第 $(j - 1)$ 列少（$0$）还是多（$1$）时的最大得分。这个情况的转移方程是
$$
f(j, i, 1) \leftarrow f(j - 1, i' \le i, 1) - s(j, 1, i') + s(j - 1, i' + 1, i) + s(j + 1, 1, i)
$$
情况 1.2：若 $i' > i$，本次操作将损失第 $j$ 列前 $i$ 行的分数，但获得了第 $(j + 1)$ 列前 $i$ 的分数。转移方程为
$$
f(j, i, 0) \leftarrow f(j - 1, i' > i, 0 \le t \le 1) - s(j, 1, i) + s(j + 1, 1, i)
$$
情况 2：当上一个操作的列是 $(j - 2)$，且它涂黑了 $i'$ 行时
情况 2.1：若 $i' \le i$，本次操作将获得第 $(j - 1)$ 列第 $(i' + 1)$ 行到第 $i$ 行的分数，以及第 $(j + 1)$ 列前 $i$ 的分数。转移方程为
$$
f(j, i, 1) \leftarrow f(j - 2, i' \le i, 0 \le t \le 1) + s(j - 1, i' + 1, i) + s(j + 1, 1, i)
$$
情况 2.2：若 $i' > i$，本次操作将获得第 $(j + 1)$ 列前 $i$ 的分数。转移方程为
$$
f(j, i, 1) \leftarrow f(j - 2, i' > i, 0 \le t \le 1) + s(j + 1, 1, i)
$$
情况 3：当上一个操作的列是 $(j - 3)$，且它涂黑了 $i'$ 行时
本次操作将获得第 $(j - 1)$ 列前 $i$ 行的分数，以及第 $(j + 1)$ 列前 $i$ 的分数。转移方程为
$$
f(j, i, 1) \leftarrow f(j - 3, i', 0 \le t \le 1) + s(j - 1, 1, i) + s(j + 1, 1, i)
$$
情况 4：这一列是第一个被操作的列
$$
f(j, i, 1) \leftarrow s(j - 1, 1, i) + s(j + 1, 1, i)
$$
所有情况取最大值即可。枚举最后操作的是哪一列，以及涂黑了几行，答案就是 $\max(f(i, j, 0/1))$。复杂度 $\mathcal{O}(n^3)$。
参考代码（c++）
###cpp
class Solution {
public:
long long maximumScore(vector<vector<int>>& grid) {
int n = grid.size();
if (n == 1) return 0;
// 前缀和预处理分数之和
long long sm[n + 2][n + 2];
memset(sm, 0, sizeof(sm));
for (int j = 1; j <= n; j++) for (int i = 1; i <= n; i++) sm[j][i] = sm[j][i - 1] + grid[i - 1][j - 1];
const long long INF = 1e18;
long long f[n + 1][n + 1][2];
for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) f[i][j][0] = f[i][j][1] = -INF;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
// 情况 4
f[i][j][1] = sm[i - 1][j] + sm[i + 1][j];
// 情况 1.1
if (i > 1) for (int jj = 1; jj <= j; jj++) {
long long det = (sm[i - 1][j] - sm[i - 1][jj]) + sm[i + 1][j] - sm[i][jj];
f[i][j][1] = max(f[i][j][1], f[i - 1][jj][1] + det);
}
// 情况 1.2
if (i > 1) for (int jj = j + 1; jj <= n; jj++) {
long long det = sm[i + 1][j] - sm[i][j];
f[i][j][0] = max({f[i][j][0], f[i - 1][jj][0] + det, f[i - 1][jj][1] + det});
}
// 情况 2.1
if (i > 2) for (int jj = 1; jj <= j; jj++) {
long long det = (sm[i - 1][j] - sm[i - 1][jj]) + sm[i + 1][j];
f[i][j][1] = max({f[i][j][1], f[i - 2][jj][0] + det, f[i - 2][jj][1] + det});
}
// 情况 2.2
if (i > 2) for (int jj = j + 1; jj <= n; jj++) {
long long det = sm[i + 1][j];
f[i][j][1] = max({f[i][j][1], f[i - 2][jj][0] + det, f[i - 2][jj][1] + det});
}
// 情况 3
if (i > 3) for (int jj = 1; jj <= n; jj++) {
long long det = sm[i - 1][j] + sm[i + 1][j];
f[i][j][1] = max({f[i][j][1], f[i - 3][jj][0] + det, f[i - 3][jj][1] + det});
}
}
long long ans = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) ans = max({ans, f[i][j][0], f[i][j][1]});
return ans;
}
};
登录
