Hỏi hướng giải quyết 1 bài trên VNOI

thangcachepckt · January 23, 2021, 1:30pm

https://codeforces.com/group/FLVn1Sc504/contest/274822/problem/P
Mọi người đưa ra cái solution chung giúp em với, em cảm ơn ạ.

Tìm số hoán vị của một dãy số cho trước thỏa mãn: không có cặp số liền kề nào trong dãy là hai số tự nhiên liên tiếp

noname00 · January 23, 2021, 11:41am

N nhỏ như vậy thì cứ backtrack thôi. Đây là solution chung nhất cho mọi loại bài có N < 20 rồi.

Ktoonovip · January 23, 2021, 11:59am

Chào bạn,
Bài này chúng ta có thể dùng dp bitmask để tối ưu hóa.
Gọi dp[i][j] là số cách chia đã sử dụng trạng thái i vào kết thúc là số thứ j. Trạng thái ở đây là lưu dạng bit (tức nếu bit thứ k bằng 1 thì đã xét số thứ k + 1)
Bây giờ chuyển trạng thái:

dp[i][j] += dp[i ^ (1 << (j - 1))][k] nếu bit k đang bật trong trạng thái i và abs(s[j] - s[k]) > k.

Kết quả của bài toán là sum toàn bộ dp[(1 << n) - 1][t] với t = 1… n.
ĐPT sẽ là O(2 ^ n * n * n). Nhưng thực tế nó không đến như vậy bởi có những trạng thái i ko cần xét hết toàn bộ các bit (nếu bạn xử lý tốt đoạn này :v)