【2022 NOIP 模拟赛 40】翻转 做题记录

zzh 有一个矩形，这个矩形被划分成了 $n\times m$ 个区域，每个区域中都写了 $0$ 或 $1$ 。

zzh 可以对这个矩形进行翻转操作，翻转操作定义如下：

选择一条只经过区域边界，从矩形左上角到矩形右下角的最短路，然后将这条路径下方的所有区域中的数翻转（$0$ 变为 $1$, $1$ 变为 $0$）。

请问最少需要多少次操作可以将这个矩阵中的所有数变为 $0$，保证一定有解。

$1\le n,m\le 5\times 10^3$。

首先可以证明一定有解，考虑贪心，每次选择顶着最上面的 $1$ 的路径：

路径不包含所有 $1$ 一定不会更优，而包含更多的 $0$ 也不会更优，所以这样一定是最优的，并且 $i$ 次操作至少可以清空左上到右下的 $i$ 条斜对角线，所以答案是 $O(n)$ 级别的。

考虑计算答案，一种显然的做法是直接模拟贪心，实现优秀则可以 $O(nm)$ 解决本题，但还有更优美的做法。

考虑用从右上到左下的最短路去截取我们选择的路径，显然这样的最短路会和每一条我们选择的路径产生恰好一个交点：（重合部分不算）

由于我们选取的路径一定有至少一个位置满足路径内部的状态与外部不同，并且从右上到左下的最短路一定可以在这些位置与我们选取的路径相交，所以所有从右上到左下的最短路中这些位置的最多个数即为答案。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

inline void fio(string name)
{
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const int S=2005;

int n,m;
char tmp[S];
int a[S][S];
int dp[S][S];

int main()
{
	fio("flip");
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",tmp+1);
		for(int j=1;j<=m;j++) a[i][j]=tmp[j]-'0';
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=1;j--)
		{
			dp[i][j]=max(dp[i-1][j]+(a[i][j]!=a[i-1][j]),dp[i][j+1]+(a[i][j]!=a[i][j+1]));
		}
	}
	printf("%d\n",dp[n][1]);
	return 0;
}