题解：AT_abc442_f [ABC442F] Diagonal Separation 2

· · 题解

F 题题解

前言：比 E 简单

题意：有一个 N 行 N 列的网格。方格 (i,j) 为白色(.)或黑色(#)。需重新涂色满足：

  1. 每行存在整数 k（0 \leq k \leq N），前 k 个方格白，其余为黑；

  2. 每列存在整数 k（0 \leq k \leq N），前 k 个方格白，其余为黑。

    求最少修改次数。

思路：第一眼能看出核心是处理行列约束，用 dp + 前缀和优化。

每行合法状态是选分界点 j（前 j 个白，后 N-j 个黑），先预处理每行每个 j 的修改成本：前 j 个黑格（需改为白）数量 s_{i,j}（前缀和），后 N-j 个白格（需改为黑）数量 N-j - (s_{i,N} - s_{i,j})，总成本为两者之和。

不妨设 f_{i,j} 表示前 i 行、第 i 行分界点为 j 的最小成本，转移时逆序遍历 j 维护前缀最小值 minn = \min_{k \geq j} f_{i-1,k}，则 f_{i,j} = minn + 该行 j 的成本，最后取 f_{N,j} 的最小值。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char a[5005][5005];
int s[5005][5005],f[5005][5005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       scanf("%s",a[i]+1);
    }
    for(int i=1;i<=n;i++)
   {
        for(int j=1;j<=n;j++)
       {
            s[i][j]=s[i][j-1]+(a[i][j]=='#'?1:0);
       }
   }
    memset(f,0x3f,sizeof(f));
    f[0][n]=0;
    for(int i=1;i<=n;i++)
   {
        int minn=1e9;
        for(int j=n;j>=0;j--)
       {
            minn=min(minn,f[i-1][j]);
            f[i][j]=min(f[i][j],minn+s[i][j]+(n-j-(s[i][n]-s[i][j])));
        }
    }
    int ans=1e11;
    for(int i=0;i<=n;i++)
    {
      ans=min(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
}