P1387 最大正方形

· · 算法·理论

虽然范围只有 100，但是还是想个 dp 比较好

设 dp_{i, j} 代表以 (i, j) 为右下角的最大正方形边长

当 s_{i,j} == 1 时， 有这样的转移方程

dp_{i,j} = min(dp_{i-1,j}, dp_{i,j-1}, dp_{i-1,j-1}) + 1

所以可以有这样的代码了

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int n, m, s[109][109];
int dp[109][109];

int main() {
    int ans = -1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> s[i][j];
            if (s[i][j] == 1)
                dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
            ans = max(ans, dp[i][j]);
        }
    cout << ans;
    return 0;
}