洛谷 P1736 创意吃鱼法（二维动态规划）

本文主要是介绍洛谷 P1736 创意吃鱼法（二维动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述 输入样例#1：
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

输出样例#1：
3

这题与LeetCode221. 最大正方形很相似，但是这道题在目标转移方程上dp[i][j]不是取dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]中的最小值+1。而是取dp[i-1][j-1]、s1[i-1][j]、s2[i][j-1]中的最小值+1，其中s1为从上至下以[i-1][j]结尾的最长连续0的个数，s2表示从左至右以[i][j-1]结尾的最长连续0的个数。还有就是这道题里，有两种对角线，主对角线和副对角线，所有要从两个方向来进行dp，最后求得最大值。
在这里插入图片描述

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<sstream>
#include<stack>
#include<stdio.h>
using namespace std;const int maxn = 2505;
int s1[maxn][maxn];
int s2[maxn][maxn];
int dp[maxn][maxn];
int g[maxn][maxn];
int ans = 0;int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {scanf("%d", &g[i][j]);if (!g[i][j]) {s1[i][j] = s1[i - 1][j] + 1;s2[i][j] = s2[i][j - 1] + 1;}else {dp[i][j] = min(dp[i - 1][j - 1], min(s1[i - 1][j], s2[i][j - 1]))+1;ans = max(ans, dp[i][j]);}				}memset(s1, 0, sizeof s1);memset(s2, 0, sizeof s2);memset(dp, 0, sizeof dp);for (int i = 1; i <= n; i++)for (int j = m; j >= 0; j--) {if (!g[i][j]) {s1[i][j] = s1[i - 1][j] + 1;s2[i][j] = s2[i][j+1] + 1;}else {dp[i][j] = min(dp[i - 1][j + 1], min(s1[i - 1][j], s2[i][j + 1]))+1;ans = max(ans, dp[i][j]);}}cout << ans;return 0;
}