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[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); }

?

轉載于:https://www.cnblogs.com/ALINGMAOMAO/p/9488649.html

總結

以上是生活随笔為你收集整理的P1387 最大正方形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。