AT_abc442_f [ABC442F] Diagonal Separation 2

tokitsukaze · 2026-01-25 14:24:25 · 题解

分享一种比较有趣（？）的思考方向。

Solution

题意相当于是求一条从左下到右上的阶梯状折线，满足左上半部分是白色，右下半部分是黑色，使得修改次数最少。

我们从折线角度考虑。会发现：从左下角出发，往上走一格，这个点往右的一行所有格子必须全是黑色；往右走一格，这个点往上的一列所有格子必须全是白色。

举个例子：

左下角开始，往右移动一格，往上移动一格，往上移动一格，往右移动一格，往上移动一格。

画一画图大概长这样：

???      .??      .??      .??      ..?      ..#
???  ->  .??  ->  .??  ->  .##  ->  .##  ->  .##
???      .??      .##      .##      .##      .##

所以只要预处理出：每个点上面一列全修改成白色的最少次数；右边一行全修改成黑色的的最少次数。然后从左下开始做 dp 即可。

最后取答案的时候要注意，最后折线的位置可能是第 n+1 列或者第 0 行。

时间复杂度 O(n^2)。

Code

AC记录

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const int MAX=5000+10;
char mp[MAX][MAX];
int w[MAX][MAX],b[MAX][MAX],dp[MAX][MAX];
int main()
{
    int n,i,j,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%s",mp[i]+1);
    memset(w,0,sizeof w);
    for(j=1;j<=n;j++)
    {
        for(i=1;i<=n;i++)
        {
            w[i][j]=w[i-1][j]+(mp[i][j]=='#');
        }
    }
    memset(b,0,sizeof b);
    for(i=1;i<=n;i++)
    {
        for(j=n;j;j--)
        {
            b[i][j]=b[i][j+1]+(mp[i][j]=='.');
        }
    }
    memset(dp,0x3f,sizeof dp);
    dp[n][1]=0;
    for(i=n;i;i--)
    {
        for(j=1;j<=n;j++)
        {
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+w[i][j]);
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+b[i][j]);
        }
    }
    ans=INF;
    for(i=0;i<=n+1;i++) ans=min(ans,dp[i][n+1]);
    for(j=0;j<=n+1;j++) ans=min(ans,dp[0][j]);
    printf("%d\n",ans);
    return 0;
}

:::