题目#
あなたはサイズ $n\times n$ の行列を持っています。行列の各セルには色 $a_{i,j}\le n$ があります。
あなたは大きな正方形が好きですが、豊富な色は好きではありません。具体的には、嫌いな値 $k \le n$ が与えられた場合、すべてのセルについて、このセルを左上隅とする最大の正方形を計算する必要があります。その正方形の内部の色の種類が $k$ を超えないようにします。
各セルについて最大正方形の辺の長さ $len$ を出力する必要があります。
注意：正方形は境界を超えてはいけません。
すべてのデータに対して、$1\le n\le 500,1\le k \le n,1\le a_{i,j}\le n$ が成り立ちます。
题解#
まず、暴力的に $n^5$ を列挙することを考えますが、明らかに不可能です。
最適化を考えます。
値域が小さいことに気づいたので、各要素を列挙し、各要素について g[i][j] を計算します。これは、この要素 A が (i, j) の点で長さ len に拡張されるときに正方形に新たに追加されることを示します。
g[i][j] = min(g[i + 1][j] + 1, g[i][j + 1] + 1, g[i + 1][j + 1] + 1);
次に、f[i][j][len] を定義します。これは、i, j の点が長さ len に拡張されるときに新たに追加される点の数を示します。
g[i][j] を計算する際に、f[i][j][g[i][j]]++ を行えば良いです。
代码#
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int a[N][N];
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
int n, k;
int g[N][N];//第A个数会在以(i, j)为左上角的正方形 边长为g[i][j] 时出现
int f[N][N][N];
int main()
{
freopen("square.in", "r", stdin);
freopen("square.out", "w", stdout);
n = read(), k = read();
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
a[i][j] = read();
}
}
for(int A = 1;A <= n;A++)
{
for(int i = n;i >= 1;i--)
{
for(int j = n;j >= 1;j--)
{
g[i][j] = 0x3f3f3f3f;
if(i + 1 <= n) g[i][j] = min(g[i][j], g[i + 1][j] + 1);
if(j + 1 <= n) g[i][j] = min(g[i][j], g[i][j + 1] + 1);
if(i + 1 <= n && j + 1 <= n) g[i][j] = min(g[i][j], g[i + 1][j + 1] + 1);
if(a[i][j] == A) g[i][j] = 1;
if(g[i][j] <= n) f[i][j][g[i][j]]++;
}
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
int len = 1, tot = f[i][j][1];//以i，j为左上角， 边长为len第一次出现了多少新颜色
while(i + len <= n && j + len <= n && f[i][j][len + 1] + tot <= k) len++, tot += f[i][j][len];
printf("%d ", len);
}
printf("\n");
}
return 0;
}