VOI 05 Bài 1 - Phân đoạn
Xem dạng PDFCho dãy số nguyên ~a_{1}, a_{2}, \dots, a_{n}~ và số nguyên dương ~k~. Ta gọi ~k~-phân đoạn của dãy số đã cho là cách chia dãy số đã cho ra thành ~k~ đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính xác hơn, một ~k~-phân đoạn được xác định bởi dãy chỉ số
~1 \le n_{1} < n_{2} < n_{3} < \dots < n_{k} = n~
Đoạn thứ ~i~ là dãy con ~a_{n_{i-1} + 1}, a_{n_{i-1} + 2}, \dots, a_{n_i}, i = 1, 2, \dots, k~. Ở đây quy ước ~n_{0} = 0~
Yêu cầu: Hãy xác định số ~M~ nhỏ nhất để tồn tại ~k~-phân đoạn sao cho tổng các phần tử trong mỗi đoạn đều không vượt quá ~M~.
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \leq k \leq n \leq 15\,000)~.
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa số nguyên ~a_{i}~ (~|a_{i}| \leq 30\,000~), ~i = 1, 2, \dots, n~.
Các số cạnh nhau trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.
Output
Gồm một số nguyên duy nhất là giá trị ~M~ tìm được.
Sample Input
9 4
1
1
1
3
2
2
1
3
1
Sample Output
5
Bình luận
ý tưởng bài này chặt nhị phân và quy hoạch động. nhưng đây chưa phải cách tối ưu.
Cách tối ưu nhất là quy hoạch động kết hợp với nén số và Binary Indexed Tree