Zumi's Blog

#training #apio #vietnamese #thầyPhương

Thầy Phương cho 3 bài của FARIO 2017. Bài 1 đã làm rồi, bài 3 là bài approximate nên mình chỉ chữa bài 2.

Pyramid Cake

Tóm tắt đề bài

Cho một chiếc hộp có đáy chữ nhật M x N, vị trí (i, j) có độ cao là H[i][j]. Ta dựng một chiếc bánh nhiều tần thỏa mãn: – Các tầng là các hình chữ nhật chứa đỉnh (1,1) – Tầng trên phải nằm bên trong mặt phẳng của tầng dưới – Không ô nào cao hơn vị trí tương ứng của hộp – Thể tích bánh là lớn nhất.

Giới hạn

1 <= N, M <= 1000, 1 <= H[i][j] <= 10^8

Lựa chọn tầng

Do mọi tầng đề chứa (1, 1), bản chất ta chỉ cần tọa độ của góc còn lại là có thể xác định được duy nhất tầng hiện tại.

Tại sao ta chỉ cần quan tâm số tầng mà không phải độ cao? Hiển nhiên, với tầng (i, j) ta biết độ cao của tầng đó (nếu tính cả các tầng dưới nó) sẽ là M[i][j] = min(H[i'][j']) với i' <= i, j' <= j.

Khi nén tầng như vậy, ta có thể coi như tầng sau luôn nhỏ hơn tầng dưới, làm cho tập trạng thái không có chu trình và ta có thể quy hoạch động được.

Gọi f[i][j] là diện tích lớn nhất của hình có tầng dưới cùng là (i, j). Hiển nhiên ta sẽ đặt tầng dưới cùng độ dày M[i][j]. Sau đó, ta chọn một tầng nhỏ hơn để qhđ:

int cur = M[i][j] * i * j; // Diện tích phần đáy
for (int k = 1; k <= i; ++k)
	for (int l = 1; l <= j; ++l)
		if (k != i || l != j)
			f[i][j] = max(f[i][j], cur + f[k][l] - M[i][j] * k * l);

Tại sao ta trừ đi M[i][j] * k * l? Bởi phần diện tích này đã được tính vào đáy của hình dưới cùng.

Đáp số sẽ là max(f[i][j]), độ phức tạp là O(N^4), chưa đủ để giải quyết bài toán.

Thử tất cả?

Ta có thể thấy, mỗi hình chữ nhật con đều nhỏ hơn đáy ban đầu ít nhất 1 hàng hoặc 1 cột. Vậy tại sao mình không chọn 1 trong 2 hình to nhất ((i, j - 1) và (i - 1, j)) để làm đáy tiếp theo?

Rất có thể mọi người sẽ nghĩ việc này không đúng vì có thể không điền đc thêm tầng nào – nhưng nếu ta nghĩ theo cách nhìn khác – ta thêm 0 tầng, thì lựa chọn vẫn hợp lí.

Có thể việc này không tối ưu không? Giả sử, lựa chọn (x, y) (x < i, y < j) là tối ưu. Hiển nhiên nó cũng sẽ tối ưu cho (i, j - 1). Vậy ta hoàn toàn có thể chọn (i, j - 1) và nó sẽ chứa cả (x, y), kết quả không đổi.

Cải thiện thuật toán

Ta rút việc chọn tất cả cặp thành chọn một trong hai hình chữ nhật con lớn nhất. Độ phức tạp giảm xuống còn O(N^2), thỏa mãn bài toán.