2018-08-16
https://www.luogu.org/problemnew/show/P1387
题意：
略。
4 4
0 0 1 1 把这个翻译成dp的形式 0 0 1 1
0 1 1 1 0 1 1 2
1 1 1 1 —> 1 1 2 2
0 1 1 1 0 1 2 3
好了，就不难理解dp[i][j]存放的就是在i*j的区域中存在的最大正方形，而找dp[i-1][j-1],dp[i-1][j],dp[i][j-1]
找这3个的最小值，就是保证以 坐标(i ,j)为右下角的正方形的左上角，右上角，左下角为1，（因为dp[i][j]是前面发展出来的）
所以，不用考虑中间可能为0的情况。好了代码如下；
#include<iostream>
#include<cstdio>
using namespace std;
int num[][];
int dp[][];
int ans;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n;++i)
for (int j = ; j <= m; ++j)
{
scanf("%d", &num[i][j]);
if (num[i][j] == )dp[i][j] = min(min(dp[i - ][j], dp[i][j - ]), dp[i - ][j - ]) + ;
ans = max(ans, dp[i][j]);
}
printf("%d\n", ans);
}