题解：AT_abc442_f [ABC442F] Diagonal Separation 2

前言

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

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

题目大意

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

题目就是说有一个

n \times n

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

解题思路

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

这里用 $pre_{i,j}$ 来表示在第 $i$ 行中前 $j$ 个格子中原本是 . 的数量（. 也可以说是白色）。
$s_i$ 表示第 $i$ 行中原本是 . 的总数。（当然如果你不想要的话也可以写 $pre_{i,n}$ 进行替换，这里只是为了方便）。我们可以使用一下代码来进行计算：

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

代码：

CPP

#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 题。

希望管理大大过。

题解：AT_abc442_f [ABC442F] Diagonal Separation 2

文章操作

前言

题目大意

解题思路

Code

end

相关推荐

评论

题解：AT_abc442_f [ABC442F] Diagonal Separation 2