#828. SEQPART – Chia dãy

Cho dãy gồm số , cần chia dãy này thành đoạn liên tiếp. Với phần tử thứ , ta định nghĩa chi phí của nó là tích của và số lượng các số nằm cùng đoạn liên tiếp với . Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử của G đoạn đã chia.

Yêu cầu: Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số và ;
• dòng tiếp theo, chứa giá trị của dãy .

Dữ liệu ra:

• Ghi ra một dòng duy nhất là chi phí nhỏ nhất.

Giới hạn:

• .

Ví dụ:

Dữ liệu vào:

6 3
11 11 11 24 26 100

Dữ liệu ra:

299

Giải thích:

• Cách tối ưu là , chi phí là .