[NTUCoder] Capxach – Cặp xách

Đề bài: http://laptrinh.ntu.edu.vn/Problem/Details/5568

Lời giải:
+ Thực ra bài này không khó nhưng mình vẫn mắc phải cái lỗi sơ đẳng nên cứ note lại vậy
+ Quy hoạch động f[x] là số cách chọn để có được khối lượng x, khởi tạo f[0] = 1, implement với 2 vòng for đơn giản
+ Chú ý:
=> Nếu dể vòng for khối lượng ở ngoài, vòng for cặp xách ở trong sẽ cho kết quả sai do bị trùng cách chọn cặp xách
=> Cách viết đúng phải là vòng for cặp xách ở ngoài, for khối lượng ở trong => như vậy việc xây dựng f[x] tại thời điểm cặp xách thứ i sẽ chỉ phụ thuộc vào cặp xách j <= i => không bị trùng cách chọn

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