Famous Pagoda (F - ACM ICPC Vietnam Regional 2017)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Khi xây dựng cầu thang đến các ngôi chùa nổi tiếng ở trên đỉnh núi, Chính quyền địa phương đã xác định \(N\) vị trí dọc theo sườn núi với các độ cao \(a_1, a_2, …, a_n\). Trong đó \(a_i< a_{i+1}\) và \(0< i< N\).
Giá để xây dựng cầu thang từ vị trí đến \(i\) vị trí \(j\) là:

\(min_{v\in \mathbb{Z}}\sum_{s=i}^{j}|a_s-v|^K\)

Để đẩy nhanh quá trình xây dựng cầu thang từ vị trí 1 đến vị trí \(N\), chính quyền địa phương đã quyết định giao việc cho \(G\) nhà xây dựng để xây dựng cầu thang song song nhau. Với \(N\) vị trí sẽ được chia thành \(G\) đoạn khác nhau và mỗi đoạn sẽ được phụ trách bởi một nhà thầu xây dựng khác nhau.

Với \(G\) nhà thầu xây dựng bạn hãy phân chia để \(G\) nhà thầu xây dựng cây cầu với tổng chi phí bé nhất.

Input

  • Dòng 1 ghi ba số nguyên \(N, G, K\) (\(1≤ N,G ≤2000, 1 ≤ K ≤ 2\)).
  • Dòng 2 ghi dãy số nguyên \(a_1 , a_2, … ,a_n\) \((1≤ a_i ≤ 10^6,a_i ≤ a_{i+1} ∀0 < i< N)\) các vị trí cần xây dựng.

Output

  • In giá trị xây dựng bé nhất.

Scoring

Example

Test 1

Input 
5 1 1
1 2 3 4 5
Output 
6

Test 2

Input 
5 1 2
1 2 3 4 5
Output 
10

Bình luận