题解：CF2096C Wonderful City

· · 题解

题意

给定一个 n 行 n 列的网格图，第 i 行 j 列的数字为 a_{i, j}。有两种操作，每种操作又分为 n 种小操作，分别编号为 1 \sim n。

每种操作的每一种小操作只能使用一次，且每种小操作都需要一定的花费。求出最少要花费多少使得操作后的网格图任意两个相邻的单元格数字相同。

思路

这道题可以考虑 dp。定义状态 (1/2,i,0/1,k) 表示选/不选第 1/2 种操作的第 i 种小操作使得前 i 行/列合法的花费为 k，如果不能实现就赋为极大值。我们对每一种操作分别开一个 dp 数组 dp1 和 dp2，dp1_{i, 0/1} 表示选/不选第 1 种操作的第 i 种小操作使得前 i 行合法的最小操作次数，dp2 同理。

考虑转移。我们先用 dp 数组代替 dp1 和 dp2，显然，dp_{i, 0/1} 是由 dp_{i - 1, 0} 和 dp_{i - 1, 1} 的最小值转移过来的，不过要注意，这里需要提前预处理出两个标记数组 f1_{i, -1/0/1} 和 f2_{i, -1/0/1}，表示对于第 i 行/列是否存在一个下标 j 使得 a_{i, j} = a_{i - 1, j} + (-1/0/1) （对于行操作）或 a_{i, j} = a_{i, j - 1} + (-1/0/1) （对于列操作）。因此，我们在转移时需要判断上一行/列做或不做操作转移过来，对于当前行/列做或不做操作是否合法。最后答案就是 \min(dp1_{n, 0}, dp1_{n, 1}) + \min(dp2_{n, 0}, dp2_{n, 1})。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005;
const ll inf = 1e18;

ll n, h[N][N], a[N], b[N], dp1[N][2], dp2[N][2];
bool vis1[N][3], vis2[N][3];

void solve(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      cin >> h[i][j];
    }
  }
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i++){
    cin >> b[i];
  }
  for(int i = 2; i <= n; i++){
    vis1[i][0] = vis1[i][1] = vis1[i][2] = 0;
    vis2[i][0] = vis2[i][1] = vis2[i][2] = 0;
    for(int j = 1; j <= n; j++){
      vis1[i][0] |= (h[i][j] == h[i - 1][j]);
      vis1[i][1] |= (h[i][j] == h[i - 1][j] - 1);
      vis1[i][2] |= (h[i][j] == h[i - 1][j] + 1);
      vis2[i][0] |= (h[j][i] == h[j][i - 1]);
      vis2[i][1] |= (h[j][i] == h[j][i - 1] - 1);
      vis2[i][2] |= (h[j][i] == h[j][i - 1] + 1);
    }
  }
  for(int i = 1; i <= n; i++){
    dp1[i][0] = dp2[i][0] = dp1[i][1] = dp2[i][1] = inf;
  }
  for(int i = 1; i <= n; i++){
    dp1[i][1] = min({(vis1[i][1] ? inf : dp1[i - 1][0]), (vis1[i][0] ? inf : dp1[i - 1][1]), inf}) + a[i];
    dp1[i][0] = min({(vis1[i][2] ? inf : dp1[i - 1][1]), (vis1[i][0] ? inf : dp1[i - 1][0]), inf});
  }
  for(int i = 1; i <= n; i++){
    dp2[i][1] = min({(vis2[i][1] ? inf : dp2[i - 1][0]), (vis2[i][0] ? inf : dp2[i - 1][1]), inf}) + b[i];
    dp2[i][0] = min({(vis2[i][2] ? inf : dp2[i - 1][1]), (vis2[i][0] ? inf : dp2[i - 1][0]), inf});
  }
  if((dp1[n][0] >= inf && dp1[n][1] >= inf) || (dp2[n][0] >= inf && dp2[n][1] >= inf)){
    cout << "-1\n";
  }else{
    cout << min(dp1[n][0], dp1[n][1]) + min(dp2[n][0], dp2[n][1]) << '\n';
  }
}

int main(){
  ios::sync_with_stdio(false), cin.tie(0);
  int T;
  cin >> T;
  while(T--){
    solve();
  }
  return 0;
}