2021牛客寒假算法基础集训营6 E 网格(dp)

Description

图片说明
一句话题意：每个网格点可以选择上下里面选一个方向，左右里面选一个方向，相邻的位于所选方向上的网格有 $w(a_{x1,y1} \oplus a_{x2, y2})$ 的贡献。

Solution

比赛时一眼就看出是 $dp$ , 但是没有仔细思考细节。
今天重新思考后发现其实不难。
对于网格点，其实行列的贡献是相互独立的，即行与列的答案hubuy并且每一行，每一列的答案不相互影响。
如果我们对行和列分开考虑的话，状态转移方程就很显然了。
令

$dp[i][0]$ 表示到第 $i$ 行的时候选择了方向为上的最优贡献
$dp[i][1]$ 表示到第 $i$ 行的时候选择了方向为下的最优贡献

那么在遍历的时候其实考虑贡献只有来自上面的单位，即 $i - 1$ 行，于是

$dp[i][0] = max(dp1[i - 1][0], dp1[i - 1][1] + 相邻两个元素的贡献$
$dp[i][1] = max(dp1[i - 1][1], dp1[i - 1][0])$

列的 $dp$ 也同理，所以对于每一列，每一行找到最优的方案统计答案即可。

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;
}