算法:DP
时间复杂度:$O(n^3)$
设 $f[i][j]$ 为以 $(i, j)$ 为右下角的正方形边长的最大值,则可表示的正方形的边长为 $1, 2, …, f[i,j]$。
其核心在于状态转移方程的推导。
如下图:
此时一定满足 $$min \lbrace f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] \rbrace + 1 == f[i][j]$$
可利用反证法证明
$min \lbrace f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] \rbrace + 1 > f[i][j]$
$\longrightarrow$ $min \lbrace f[i - 1][j], f[i][j - 1], f[i - 1][j - 1] \rbrace \ge f[i][j]$
则上述式子一定不成立,因为不可能存在 $==$,更不可能 $>$,如果存在,则 $f[i,j]$ 一定不是当前最大。
此时会呈现下图状:
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300;
int n, ans[N], f[N][N];
char g[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> g[i] + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (g[i][j] == '1') {
f[i][j] = min(f[i - 1][j], min(f[i][j - 1], f[i - 1][j - 1])) + 1;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= f[i][j]; ++k) {
ans[k]++;
}
}
}
for (int i = 2; ans[i]; ++i) cout << i << ' ' << ans[i] << endl;
return 0;
}