题解：AT_abc442_f [ABC442F] Diagonal Separation 2

kobelukuankuan · 2026-01-25 16:28:00 · 题解

前言

赛时该死的 ABC 网络给我卡没了，结果导致我在赛后一分钟 F 题 AC 了，不过比赛已经结束了，为此感到十分不幸。

为了弥补不幸，本五年级蒟蒻还是又来写一篇题解来安慰一下我吧。

题目大意

一读题就发现应该不难，可谓最简单的 F 题。

题目就是说有一个 n \times n 的方格，每个格子要么是 .，要么是 #。现在需要让你把一些方格的颜色替换成另一个颜色（重新涂色），但是必须保证每一行的前一连续的部分是一个颜色，后一部分都是另一个颜色。此外，列也一样。

解题思路

我们为了快速计算修改代价，因此可以用前缀和来预处理每一行的操作参数：

这里用 pre_{i,j} 来表示在第 i 行中前 j 个格子中原本是 . 的数量（. 也可以说是白色）。
我们可以使用一下代码来进行计算： ```cpp for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) pre[i][j]=pre[i][j-1]+(c[i][j]=='.'); s[i]=pre[i][n]; } ``` 这里没什么难点就不详细讲了，就是普通的前缀和。

那么我们求出了这两个参数以后，后面计算我们需要的花费就很简单了。

设对于第 i 行，中间进行分段的点为 j，则：

在前 j 个格子中，初始为黑色的需要改成白色：j - pre_{i,j}。
后 n - j 个格子中，初始为白色的需要改成黑色：s_i - pre_{i,j}。

所以总花费为 (j − pre_{i,j}) + (s_i−pre_{i,j})，将该式简化可得 j + s_i − 2 \times pre_{i,j}。这里为了后边的讲解，我们将总花费设为 x。

接下来就可以开始考虑动态规划。

众所周知，由于我们的行分界点一定是非递减的的，因此第 i - 1 行的分界点 k 必须满足 k \le j。

因此不难推导出状态转移方程：

dp_{i,j} = \min_{0 \le k \le j} dp_{i-1,k} + x

然而我们发现，直接计算是 O(n^3) 是一定会超时的，就算对于 5000 也会，因此我们接下来考虑优化。

注意到对于固定的 i，我们需要对每个 j 求 dp_{ i - 1,0 \cdots j} 的最小值。因此我们不难发现可以预处理一下前缀最小值。这里前缀最小值的数组为 d。因此方程推导：

d_i = \min_{0 \le k \le j} dp_{i-1,k}

因此我们的 dp 数组新的状态转移方程也就得来了：

dp_{i,j} = d_j + x

具体内部的实现我在这里总结了一下：

对于每一行 i，我们可以先计算这一行所有 j 的总花费，记作 p_j。
从上到下计算 d 数组：d_j = \min(d_{j-1}, dp_{i-1,j})。
更新 dp_{i,j} = d_j + p_j。这里的 p_j 其实跟刚才的 x 含义一模一样。

然后要注意 dp 数组的初始化。先可以初始化第 1 行，dp_{1,i}=(i - pre_{1,i}) + (s_1 - pre_{1,i})。

最后的答案也就是：

ans = \min_{0 \le j \le n} dp_{n,j}

这样我们就简单高效的解决了问题，代码时间复杂度为 O(n^2)，不会超时。

Code

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010,INF=1e18;
int n;
char c[N][N];
int pre[N][N],s[N];
int dp[N][N];
int p[N];
int d[N];
int ans=INF;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) cin>>c[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) pre[i][j]=pre[i][j-1]+(c[i][j]=='.');
        s[i]=pre[i][n];
    }
    for(int i=0;i<=n;i++)
    {
        dp[1][i]=(i-pre[1][i])+(s[1]-pre[1][i]);
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=n;j++) p[j]=(j-pre[i][j])+(s[i]-pre[i][j]);
        d[n]=dp[i-1][n];
        for(int j=n-1;j>=0;j--) d[j]=min(d[j+1],dp[i-1][j]);
        for(int j=0;j<=n;j++) dp[i][j]=d[j]+p[j];
    }
    for(int j=0;j<=n;j++)
    {
        if(dp[n][j]<ans) ans=dp[n][j];
    }
    cout<<ans;
    return 0;
}

具体的上面思路已经讲的很清楚了，就不写注释了。

提交记录

end

感谢大家的阅读，我也是写的应该很清楚了，花费了很多心思。纪念一下第一次过 F 题。

希望管理大大过。