trang chủ / bài tập / balsubsets / lời giải

Tập Con Cân Bằng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả:

huunguyen

Lời giải: Tập con cân bằng

Hướng tiếp cận

Bài toán yêu cầu đếm số tập con thỏa mãn 4 điều kiện. Ta sẽ phân tích cấu trúc của tập con hợp lệ rồi dùng quy hoạch động.

Nhận xét quan trọng

Nhận xét 1: Trong mỗi hàng có ít nhất một ô thuộc tập con, tập hợp các ô đó phải tạo thành một đoạn liên tục $[L_{i}, R_{i}]$ (từ điều kiện 3 và 4).

Nhận xét 2: Các hàng chứa ô thuộc tập con phải là liên tiếp nhau (từ điều kiện 2 - liên thông 4 chiều).

Nhận xét 3: Hai hàng liên tiếp $i$ và $i + 1$ phải có đoạn giao nhau: $L_{i + 1} \leq R_{i}$ và $R_{i + 1} \geq L_{i}$ .

Nhận xét 4 (quan trọng nhất): Dãy $L_{1}, L_{2}, \dots, L_{k}$ phải là dãy lưỡng điệu giảm rồi tăng (non-increasing rồi non-decreasing). Tương tự, dãy $R_{1}, R_{2}, \dots, R_{k}$ phải là dãy lưỡng điệu tăng rồi giảm.

Chứng minh nhận xét 4: Nếu $L$ có dạng tăng-giảm-tăng (không đơn điệu 2 pha), thì tồn tại $i < j < k$ sao cho $L_{i} < L_{j}$ và $L_{j} > L_{k}$ . Từ điều kiện 3, cột $L_{j}$ xuất hiện ở hàng $j$ nhưng không xuất hiện ở hàng $i$ hay $k$ . Tuy nhiên để liên thông, phải có đường đi từ một ô ở hàng $i$ qua hàng $j$ đến hàng $k$ , mà đường đi đó khi đi qua cột $L_{j}$ sẽ tạo ra các ô ở cột $L_{j}$ ở tất cả các hàng giữa — mâu thuẫn. Lập luận tương tự cho $R$ .

Thuật toán

Trạng thái DP: $d p [a] [b] [l] [r]$ = số tập con cân bằng có hàng đáy là hàng hiện tại $h$ , đoạn cột của hàng đáy là $[l, r]$ , trong đó:

$a = 0$ : dãy $L$ vẫn đang trong pha không tăng; $a = 1$ : dãy $L$ đã chuyển sang pha không giảm
$b = 0$ : dãy $R$ vẫn đang trong pha không giảm; $b = 1$ : dãy $R$ đã chuyển sang pha không tăng

Chuyển trạng thái: Từ hàng $h - 1$ sang hàng $h$ , nếu hàng trước có đoạn $[l^{'}, r^{'}]$ và hàng hiện tại có đoạn $[l, r]$ :

Từ $(a^{'}, b^{'})$	Sang $(a, b)$	Điều kiện
$(0, 0)$	$(0, 0)$	$l^{'} \geq l$ , $r^{'} \leq r$
$(0, 0)$	$(0, 1)$	$l^{'} \in [l, r]$ , $r^{'} > r$
$(0, 0)$	$(1, 0)$	$l^{'} < l$ , $r^{'} \in [l, r]$
$(0, 0)$	$(1, 1)$	$l^{'} < l$ , $r^{'} > r$
$(0, 1)$	$(0, 1)$	$l^{'} \in [l, r]$ , $r^{'} \geq r$
$(0, 1)$	$(1, 1)$	$l^{'} < l$ , $r^{'} \geq r$
$(1, 0)$	$(1, 0)$	$l^{'} \leq l$ , $r^{'} \in [l, r]$
$(1, 0)$	$(1, 1)$	$l^{'} \leq l$ , $r^{'} > r$
$(1, 1)$	$(1, 1)$	$l^{'} \leq l$ , $r^{'} \geq r$

Tối ưu hoá: Mỗi truy vấn chuyển trạng thái là tổng một vùng chữ nhật trên mảng $d p [a^{'}] [b^{'}]$ . Ta dùng 4 loại bảng prefix sum (suffix-L prefix-R, suffix-L suffix-R, prefix-L prefix-R, prefix-L suffix-R) để trả lời mỗi truy vấn trong $O (1)$ . Tổng độ phức tạp là $O (N^{3})$ .

Mỗi hàng $h$ : xây dựng bảng prefix sum $O (N^{2})$ , rồi duyệt tất cả $(l, r)$ hợp lệ $O (N^{2})$ với chuyển trạng thái $O (1)$ → tổng $O (N^{3})$ .

Độ phức tạp

Thời gian: $O (N^{3})$
Bộ nhớ: $O (N^{2})$ cho bảng DP và prefix sum

Bình luận

Không có bình luận tại thời điểm này.