洛谷 P1736 创意吃鱼法

鱼塘传送门

简析

历经千辛万苦鬼搞一通之后发现自己没有预处理就把这题给过了,感觉是个很厉害的壮举(不),在这里简单说一下自己的思路。

方便起见,我们先考虑左上右下对角线的情况。
首先,我们将原来的鱼塘用数组 (v) 储存起来,数组 (f) 储存当前点的左上方满足条件的最大子矩阵对角线的长度,显而易见地有如下初始化过程:

(f[i][j] = v[i][j])

假如当前点满足如下两个条件:

(1. f[i - 1][j - 1] > 0)

(2. v[i][j] > 0)

这个时候,我们可以尝试更新 (f[i-1][j-1]),简单思考一下,我们发现,我们只用检查 (v[i][j]) 上方 (f[i-1][j-1]) 个格子和右方 (f[i-1][j-1]) 个格子,只要检查到的格子全为 (0) 就可以进行更新:

(f[i][j] = f[i-1][j-1] + 1)

(想一想,为什么?)

但如果检查上述格子之后发现有 (1) ,怎么办呢?放任不管吗?显然不是。

经过思考,我们发现 (v[i][j]) 上方和右方遇到最近的 (1) 格依旧可以用来更新答案。不清楚原因?没关系,我们来看一个简单的例子:

v:     f:
1 0 1  1 0 1
0 1 0  0 2 0
1 0 0  ? x x

现在,我们考虑 (?) 位置的格子,按照上述方案,我们试着检查 (v[3][3]) 上方和右方的格子,发现上方两格处有最近的 (1)

显然这个时候我们不能按刚才给出的公式进行转移,但由肉眼分析我们不难发现 (f[3][3]) 中应当填写的值是 (2)

发现规律了吗?应当填写的值就是上方和右方遇到最近的 (1) ,与你当前考虑的格子的行数(或列数)之差的绝对值。

对于右上坐下对角线情况的分析大同小异,留给读者自己思考。

AC代码

#include<iostream>
using namespace std;
int n,m,ans;
bool v[2501][2501];
int f[2501][2501];
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++){
			cin >> v[i][j];
			f[i][j] = v[i][j];
		}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(v[i][j] && f[i - 1][j - 1]){
				bool flag = 1;int l = 0x3f3f3f3f;
				for(int k = i - 1;k >= i - f[i - 1][j - 1] && flag;k--)
					if(v[k][j]) flag = 0,l = min(l,i - k);
				for(int k = j - 1;k >= j - f[i - 1][j - 1] && flag;k--)
					if(v[i][k]) flag = 0,l = min(l,j - k);
				if(flag) f[i][j] = f[i - 1][j - 1] + 1;
				else f[i][j] = l;
			}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			ans = max(f[i][j],ans);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			f[i][j] = v[i][j];
	for(int i = 1;i <= n;i++)
		for(int j = m;j >= 1;j--)
			if(v[i][j] && f[i - 1][j + 1]){
				bool flag = 1;int l = 0x3f3f3f3f;
				for(int k = i - 1;k >= i - f[i - 1][j + 1] && flag;k--)
					if(v[k][j]) flag = 0,l = min(l,i - k);
				for(int k = j + 1;k <= j + f[i - 1][j + 1] && flag;k++)
					if(v[i][k]) flag = 0,l = min(l,k - j);
				if(flag) f[i][j] = f[i - 1][j + 1] + 1;
				else f[i][j] = l;
			}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			ans = max(f[i][j],ans);
	cout << ans;
	return 0;
} 
原文地址:https://www.cnblogs.com/mysterious-garden/p/9871530.html