【离散】【差分】不同数字

给出一个 h×w 的矩阵，矩阵中每个元素的大小介于 1 到 256 之间。

现在请你遮去一个面积不超过 s 的矩形，使得未被遮住的部分中不同的数字个数尽可能的少。

然后输出这个剩余的不同数字的个数。

10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

4

遮住的矩形是图中黑色部分，剩余的不同的数字有 1,3,4,5 共 4 个

1 < = h , w < = 1000 1 <= h, w <= 1000 1<=h,w<=1000
1 < = a i , j < = 256 1 <= a_{i,j} <= 256 1<=ai,j​<=256
1 < = s < = h ∗ w 1<=s<=h*w 1<=s<=h∗w

观察数据，由于颜色数十分小，遂考虑从颜色数上下手。
直接枚举行，列肯定超时， 我们很难接受1000 * 1000再乘上更多的数。
我们可以记录一下每种颜色若要被全部覆盖需要的最小矩形的坐标。所以当我们找的矩形包括了某种颜色全覆盖所需要的最小矩形，那么这种颜色就被全覆盖了。
记录坐标后，不难发现，可以使用离散化，枚举行。
这样，任取两行的复杂度就是 256 * 256， （即起始行数*结束行数）可以接受。
当我们枚举了行之后我们就可以求得能包括的列数了。
接下来只用考虑那种颜色在这两行内被包括即可。
接着使用差分记录一下符合条件的颜色的位置，滚一遍即可。
时间复杂度 O ( 256 ∗ 256 ∗ 1000 ) O(256*256*1000) O(256∗256∗1000) 。

#include
using namespace std;
int chafen[1005], A[260], D[260], W[260], S[260], H[520];
int t2, l2, ttc, ans, h, w, s, c, cnt, lj, len;
bool cmp(int xx, int yy){
	if(A[xx] != A[yy])
	return A[xx] < A[yy];
	return D[xx] < D[yy];
}
int main(){
	memset(A, 0x7f, sizeof(A));
	memset(W, 0x7f, sizeof(W));
	scanf("%d%d%d", &h, &w, &s);
	for(int i = 1; i <= h; ++i)
		for(int j = 1; j <= w; ++j){
			scanf("%d", &c);
			A[c] = min(A[c], j);
			D[c] = max(D[c], j);
			W[c] = min(W[c], i);
			S[c] = max(S[c], i);
		}
	for(int c = 1; c <= 256; ++c)
		if(A[c] <= D[c]){
			H[++t2] = W[c];
			H[++t2] = S[c];
			++ttc;
		}
	ans = ttc;
	sort(H+1, H+1+t2);
	t2 = unique(H+1, H+1+t2) - H;
	--t2;
	for(int i = 1; i <= t2; ++i)
		for(int j = i; j <= t2 && H[j]-H[i]+1 <= s; ++j){
			len = s / (H[j]-H[i]+1);
			memset(chafen, 0, sizeof(chafen)); 
			int kkk = 0;
			for(int c = 1; c <= 256; ++c)
				if(W[c] >= H[i] && S[c] <= H[j] && W[c] <= S[c] && D[c] - A[c] + 1 <= len){
					if(D[c] <= len) ++chafen[1];
					else ++chafen[D[c]-len+1];
					--chafen[A[c]+1];
				}
			for(int i = 1; i <= w; ++i){
				kkk += chafen[i];
				ans = min(ans, ttc - kkk);
			}
		}
	printf("%d", ans);
}