Description
一句话题意:每个网格点可以选择上下里面选一个方向,左右里面选一个方向,相邻的位于所选方向上的网格有 的贡献。
Solution
比赛时一眼就看出是 , 但是没有仔细思考细节。
今天重新思考后发现其实不难。
对于网格点,其实行列的贡献是相互独立的,即行与列的答案hubuy并且每一行,每一列的答案不相互影响。
如果我们对行和列分开考虑的话,状态转移方程就很显然了。
令
- 表示到第 行的时候选择了方向为上的最优贡献
- 表示到第 行的时候选择了方向为下的最优贡献
那么在遍历的时候其实考虑贡献只有来自上面的单位,即 行,于是
列的 也同理,所以对于每一列,每一行找到最优的方案统计答案即可。
Code
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const int mod = 998244353; int dp1[1005][2], dp2[1005][2]; int cal(int x) { return x + __builtin_popcount(x); } void solve() { int n, m; cin >> n >> m; vector<vector<int> > maze(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; } } int ans = 0; for (int j = 0; j < m; j++) { int maxz = 0; for (int i = 0; i < n; i++) { if (i - 1 >= 0) { // 0: up, 1: down dp1[i][0] = max(dp1[i - 1][0], dp1[i - 1][1] + cal(maze[i][j] ^ maze[i - 1][j])); dp1[i][1] = max(dp1[i - 1][1], dp1[i - 1][0]); } else { dp1[i][0] = dp1[i][1] = 0; } } for (int i = 0; i < n; i++) { maxz = max(maxz, dp1[i][0]); maxz = max(maxz, dp1[i][1]); } ans += maxz; } for (int i = 0; i < n; i++) { int maxz = 0; for (int j = 0; j < m; j++) { if (j - 1 >= 0) { // 0: left, 1: right dp2[j][0] = max(dp2[j - 1][0], dp2[j - 1][1] + cal(maze[i][j] ^ maze[i][j - 1])); dp2[j][1] = max(dp2[j - 1][0], dp2[j - 1][1]); } else { dp2[j][0] = dp2[j][1] = 0; } } for (int j = 0; j < m; j++) { maxz = max(maxz, dp2[j][0]); maxz = max(maxz, dp2[j][1]); } ans += maxz; } cout << ans << '\n'; } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int T = 1; //cin >> T; while (T--) { solve(); } return 0; }