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
     
      #include
      
       using namespace std;int num[102][102];int dp[102][102];int ans;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", &num[i][j]);        if (num[i][j] == 1)dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;        ans = max(ans, dp[i][j]);    }    printf("%d\n", ans);}