Editorial for CHOOSE - Chọn phần tử
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Với bài này ta sẽ sử dụng quy hoạch động 2 lần:
- Gọi ~f[i][j][cnt][base]~ là tổng lớn nhất các phần tử ở hàng ~i~ lấy ~cnt~ phần tử từ ~1~ đến ~j~ mà tổng này chia ~k~ dư ~base~.
- Gọi ~F[i][base]~ là tổng lớn nhất mà chọn các phần từ ở các hàng từ ~1~ đến ~i~ mà tổng này chia ~k~ dư ~base~.
Kết quả là ~F[n][0]~. Các bạn tự tìm công thức quy hoạch động nhé.
Comments