题解：AT_abc442_f [ABC442F] Diagonal Separation 2

Snowday · 2026-01-25 19:10:22 · 题解

我们考虑修改完的地图一定如下，红色代表白色。

就是一个倒着的阶梯状分割线，分割线左边是白色，右边是黑色。

我们考虑动态规划，设 dp[i][j] 表示，使第 i 行，前 j 个是白色，后 n-j 个是黑色，并且前 i-1 行也满足题目约束所需的最小代价。

我们拆解一下代价，发现可以分成两部分。一部分是使前 i-1 行都合法的代价，另一部分是使第 i 行合法的代价。

先考虑后一部分，因为这是一个倒阶梯状，我们设第 i 行保留白色的个数是 a_i，我们发现 a_i 是不升的。我们假设第 i 行前 j 个是白色，那么 dp[i][j]= \min_{k=j}^{n} (dp[i - 1][k]) + cost。我们发现只需要维护一个后缀最值即可。设 mn[j] 表示 \min_{i=j}^{n} dp[i][j]，那么 mn[n] =dp[i][n]，其余 mn[j]=min(mn[j+1],dp[i][j])。每次查询就是 mn[j] 即可。

然后考虑前一部分，这个相对简单一点，我们只需要把第 i 行前 j 个点中，所有黑色点全部变成白色点。把后 n-j 个点中，所有白色点变成黑色点。代价就是前 j 个点中黑色点的数量，加上后 n-j 个点中白色点的数量。至于怎么维护也很简单，我们用一个二维前缀和数组，维护黑色或者白色点的数量，注意细节就行，我代码里有。

代码如下。

#include<bits/stdc++.h>
using namespace std;

#define _for(i,a,b) for(int i = (a) ; i <= (b) ; i ++)
#define for_(i,a,b) for(int i = (a) ; i >= (b) ; i --)
#define ls k << 1
#define rs k << 1 | 1
const int inf = 1e9;
int n,ans = inf;
const int maxn = 5e3 + 10;
int dp[maxn][maxn];
int a[maxn][maxn];
int sum[maxn][maxn];
int min_dp[maxn];
int get_pay(int i,int j){ 
    int tmp1 = sum[i][j] - sum[i - 1][j];//前j个黑点数量 
    int tmp2 = sum[i][n] - sum[i - 1][n] - tmp1;//后n-j个黑点数量 
    int tmp3 = (n - j) - tmp2;//后n-j个白点数量 
    return tmp1 + tmp3;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    memset(dp,0x3f,sizeof dp);
    cin >> n;
    _for(i , 0 , n) dp[0][i] = 0;
    _for(i , 1 , n){
        string s;
        cin >> s;
        _for(j , 1 , n) {
            if(s[j - 1] == '#') a[i][j] = 1;
        }
    }
    _for(i , 1 , n){
        _for(j , 1 , n) {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }   
    _for(i , 1 , n){
        _for(j , 0 , n){
            int tmp = get_pay(i,j);
            if(i == 1) dp[i][j] = tmp;
            else dp[i][j] = min_dp[j] + tmp;
        }
        min_dp[n] = dp[i][n];
        for_(j , n - 1 , 0) min_dp[j] = min(dp[i][j],min_dp[j + 1]);
    } 
    cout << min_dp[0];
    return 0;
}