hihocoder 1469 福字 (dp)

hihocoder 1469 福字 (dp)

描述

新年到了，你收到了一副画。你想找到里面最大的福字。一副画是一个n × n的矩阵，其中每个位置都是一个非负整数。一个福字被定义成是大小为 k 的正方形，满足其中的每个位置上的数都恰好比他的左边的那个和上边的那个大1（如果左边或上边的那个不存在的话就无此要求）。比如1 2 3 2 3 4 3 4 5就是一个福字。（注意左上角可以是任何非负整数）。你想找到这个矩阵中最大的福字的大小。

输入

第一行一个数 n，表示矩阵大小。(n ≤ 1000)接下来 n 行，每行 n 个数，表示这个矩阵。矩阵中的数在0到108之间。

输出

一行一个数表示最大的福字的大小。

样例输入

41 2 3 02 3 4 03 4 5 00 0 0 0

样例输出

3

思路

​​dp[i][j]​​表示以第i行第j列元素为矩阵右下角所能得到的最大福字的大小。

对于这一个矩阵，​​dp[i][j]​​​对于​​dp[i-1][j]​​来说属于竖向扩充。

同理，​​dp[i][j]​​​对于​​dp[i][j-1]​​来说属于横向扩充。

因此，在​​a[i-1][j]+1==a[i][j]&&a[i][j-1]+1==a[i][j]​​​成立的前提下（扩充福字），​​dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1​​

其他条件便只能由所在一个元素去构成一个福字矩阵了，大小​​dp[i][j]=1​​

AC 代码

#include#define N 1005using namespace std;int n,ans,a[N][N],dp[N][N];int main(){ scanf("%d",&n); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { scanf("%d",&a[i][j]); if(a[i-1][j]+1==a[i][j]&&a[i][j-1]+1==a[i][j]) dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1; else dp[i][j]=1; ans=max(ans,dp[i][j]); } printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。