[VOJ][TC]TWOSIDE
le tue
Bài này em vẫn chưa cài thử, mới chỉ nghĩ thuật toán thôi!
Đề bài: http://vn.spoj.pl/problems/TWOSIDE
Xây dựng đồ thị vô hướng N đỉnh (như vậy đỉnh tượng trưng cho các số
trên lá bài). Với mỗi lá bài, ta nối 2 đỉnh của đồ thị được viết trên
lá bài (như vậy lá bài tượng trưng cho cạnh).
Có nhận xét như sau: do mỗi số được viết trên các lá bài đúng 2 lần
nên bậc của mỗi đỉnh trên đồ thị đều đúng bằng 2. Do tính chất bậc như
vậy thì đồ thị sẽ là một số chu trình rời nhau.
Đánh số các chu trình từ 1 đến C.
Chúng ta hình dung sẽ có N chỗ trống để đặt các quân bài vào.
Xét lần lượt từng chu trình.
Giả sử đang xét đến chu trình thứ t, giả sử chu trình này có P số và
lúc này còn lại M chỗ trống. Chúng ta sẽ đếm số cách đặt P số lên M
chỗ trống còn lại. Rõ ràng là có C(P,M) cách chọn P chỗ trống để điền
vào M chỗ trống còn lại. Như vậy chỉ cần đếm số hoán vị của P số.
Nhận xét là:
- Các số chỉ có thể xuất hiện 0 lần, 1 lần hoặc 2 lần.
- Các số kề nhau trên chu trình không thể cùng xuất hiện 2 lần.
Tiếp tục với việc xét chu trình thứ t hiện tại, qua các nhận xét đó,
ta thấy bài toán cần giải là như sau (chỉ cần giải bài toán này là
giải được bài toán gốc):
Có P vị trí trên vòng tròn. Đếm số cách điền các số 0,1,2 vào P vị trí
đó sao cho tổng các số được điền là P và không có 2 số 2 nào đứng cạnh
nhau.
Để thuận tiện, gọi số được điền ở vị trí i trên vòng tròn là x[i].
Từ các ràng buộc của bài toán mới, ta có một hàm quy hoạch động để đếm
như sau:
F[i,s,v1,vi]: số cách thỏa mãn đã điền i số đầu tiên trên hình tròn, i
số này có tổng là s, x[1]=v1, x[i]=vi.
Công thức để tính F như sau:
F[i,s,v1,vi] = ∑ f[i,s-vi,v1,vi’] với 0<=vi’<=2, vi’<>vi.
Như vậy kết quả của bài toán mới sẽ thu được là: F[P,P,v1,vp] với
0<=v1<=2, 0<=vp<=2, v1<>vp.