Tối ưu hóa quy hoạch động Chia để trị (Divide and Conquer DP)

Mục tiêu kiến thức

• Nhận diện tính chất bất đẳng thức tứ giác (Quadrangle Inequality) C(a, c) + C(b, d) ≤ C(a, d) + C(b, c) với a ≤ b ≤ c ≤ d.
• Chứng minh tính đơn điệu của điểm chuyển trạng thái tối ưu: opt(i, j) ≤ opt(i, j + 1).
• Tối ưu hóa độ phức tạp quy hoạch động phân hoạch K đoạn từ O(K · N²) xuống O(K · N log N).

Mô tả bài toán

Cho một dãy gồm N số nguyên dương A₁, A₂, …, A_N. Bạn cần phân chia dãy này thành đúng K đoạn con liên tiếp không rỗng. Chi phí của một đoạn từ chỉ số l đến r (1-indexed) là bình phương tổng các phần tử trong đoạn: C(l, r) = ( ∑_i=l^r A_i )² Hãy tìm tổng chi phí nhỏ nhất để phân chia toàn bộ dãy thành K đoạn con.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ K ≤ N ≤ 3000.
• Thời gian: 1000ms. Bộ nhớ: 256MB.