正方形 - histcat

題目#

你有一個大小為 $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;
}