题解：AT_abc442_f [ABC442F] Diagonal Separation 2

he_lucky · 2026-01-25 20:46:01 · 题解

题目描述：

有一个 n\times n 的网格图，每个格子要么是白色，要么是黑色。
现在要重新涂色，使得满足一下条件：

• 每一行：白色格子都在左边，黑色格子都在右边；
• 每一列：白色格子都在上面，黑色格子都在下面。
  问：最少需要重新涂多少个格子？

例如：

..#
.##
###

就是一个满足要求的网格图。

.##
..#
###

则是一个不满足要求的网格图，因为第二行白色格子不在上面。

思路：

原问题：最少改多少个格子？
我们可以用动态规划的思想。

dp[i][j] 表示对于第 i 行，第一个是黑色的列数是 j 的最少重新涂色的次数。

仔细观察网格图，发现：

.##
..#
###

上面这个网格图是不满足要求的，所以可以得出结论：
第 i 行的第一个黑色格子的位置 \le 第 i-1 行的第一个黑色格子的位置。

步骤：

1. 输入，将黑色格子当作 1，将白色格子当作 0。
2. 倒着枚举列，计算前 i-1 行的次数。
3. 如果当前的 j 为第一个黑色，那么枚举 1 到 j-1，如果有黑色，需要重涂的次数加一，枚举 j 到 n，如果有白色，重涂的次数加一。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int N = 5010;
int n;
int dp[N][N];
int a[N][N];
int b[N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            char c;
            cin >> c;
            if (c == '.'){
                a[i][j] = 0;
            }else{
                a[i][j] = 1;
            }
        }
    }
    for (int i = 1;i <= n;i++){
        int ans = dp[i-1][n+1];
        for (int j = n+1;j >= 1;j--){
            ans = min(ans,dp[i-1][j]);
            int t = 0;
            for (int k = 1;k < j;k++){
                if (a[i][k] == 1) t++;
            }
            for (int k = j;k <= n;k++){
                if (a[i][k] == 0) t++;
            }
            dp[i][j] = ans + t;
        }
    }
    int ans = INT_MAX;
    for (int i = 1;i <= n+1;i++){
        ans = min(ans,dp[n][i]);
    }
    cout << ans <<endl;
    return 0;
}

显然上面代码超时，使用前缀和优化。
前缀和记录每行的黑色格子。
所以记录时不需要两个循环了。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int N = 5010;
int n;
int dp[N][N];
int a[N][N];
int b[N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            char c;
            cin >> c;
            if (c == '.'){
                a[i][j] = 0;
            }else{
                a[i][j] = 1;
            }
            b[i][j] = b[i][j-1] + a[i][j];//前缀和
        }
    }
    for (int i = 1;i <= n;i++){
        int ans = dp[i-1][n+1];//直接记录上一行n+1位置
        for (int j = n+1;j >= 1;j--){
            ans = min(ans,dp[i-1][j]);
            int t = 0;
            t = b[i][j-1] + (n-j+1-(b[i][n]-b[i][j-1]));
            dp[i][j] = ans + t;
        }
    }
    int ans = INT_MAX;
    for (int i = 1;i <= n+1;i++){
        ans = min(ans,dp[n][i]); // 最后答案
    }
    cout << ans <<endl;
    return 0;
}