[SPOJ] QBGAME – Trò chơi trên ma trận

Đề bài: http://vn.spoj.com/problems/QBGAME/

Thuật toán: Quy hoạch động trạng thái – Độ phức tạp O(N*55^2) ~ O(29.160.000)
Thuật toán chi tiết có trong quyển KC-Book 3 nên mình sẽ không nêu ra nữa. Sau khi AC và search gg thì thấy ít người up full code lên, và mình chưa thấy ai cài đặt tối ưu ( nhất là phần xử lí bit ), nên mạn phép up code của mình lên vậy >:)

Source code: http://ouo.io/Yerq63

Một số chú ý để tối ưu bài toán khi cài đặt:
– Thay vì duyệt trâu 2^8 = 256 trạng thái, ta chỉ cần chọn ra những trạng thái phù hợp với điều kiện bài toán ( không có 2 ô nào chung cạnh ), tức là trạng thái mà không có những bit 1 liền kề nhau. Điều kiện này có thể được kiểm tra với trạng thái s như sau: s&(s>>1) == 0 ( dễ dàng chứng minh )
– Kiểm tra xem trạng thái s và trạng thái trước nó ( preS ) có thoả mãn là 2 trạng thái này không chứa 2 ô có cạnh chung hay không, có thể dễ dàng kiểm tra bằng điều kiện : ( s & preS ) == 0
– Nên tính trước mảng sum[j][s] là tổng giá trị của các ô được chọn ( thể hiện trong cấu hình s ) tại cột thứ j. Tránh lồng vào phần xử lí chính

Hành trình AC:
– 6.67 : Không nhận ra rằng tại cột thứ j, có thể không chọn ô nào cả, nên đã không cho vào trạng thái 00000000 ( 0 ). Sửa lại: s từ 00000001 đến 11111111, preS từ 0 đến 11111111 <= Đáng chú ý vì có một số bài dp trạng thái đã làm trước đó không cần đưa cấu hình 0 ( vì cấu hình 0 không tắt bit ) <= Ngựa quen đường cũ :))
– 44.67: Oh shit ! s cũng cần phải duyệt từ 0, vì mỗi cấu hình ứng với nhiều cột khác nhau.
– 66.67: Wth ? Bình tĩnh, bình tĩnh, còn trường hợp mảng a âm nữa mà T.T
– 100.0- AC 🙂

Happy coding :v

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s