洛谷 1736 创意吃鱼法#坐标型动态规划#

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

题目

在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。她一口下去，最多可以吃掉多少条鱼？

分析

这道题可以用动态规划，不过要预处理横着的和竖着的
$f[i][j]=\min(f[i-1][j-1],s1[i][j-1],s2[i-1][j])+1$
或 $f[i][j]=\min(f[i-1][j+1],s1[i][j+1],s2[i-1][j])+1$

代码

#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
int n,m,ans;
int a[2501][2501],f[2501][2501];
int s1[2501][2501],s2[2501][2501];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int min(int a,int b){return (a>b)?b:a;}
int max(int a,int b){return (a<b)?b:a;}
int main()
{n=in(); m=in();for(int i=1;i<=n;i++)//左上 to 右下for(int j=1;j<=m;j++){a[i][j]=in();if(!a[i][j]){s1[i][j]=s1[i][j-1]+1;s2[i][j]=s2[i-1][j]+1;}if(a[i][j])f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;ans=max(ans,f[i][j]);}memset(f,0,sizeof(f)); memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); for(int i=1;i<=n;i++)//左下 to 右上for(int j=m;j>=1;j--){if(!a[i][j]){s1[i][j]=s1[i][j+1]+1;s2[i][j]=s2[i-1][j]+1;}if(a[i][j])f[i][j]=min(f[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;ans=max(ans,f[i][j]);}return !printf("%d",ans);
}