Chuồng Bò Tròn Mới

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Chuồng bò của Farmer John gồm $N$ phòng được đánh số từ $1$ đến $N$ xếp thành một vòng tròn theo chiều kim đồng hồ (phòng $N$ kề với phòng $1$ ). Mỗi phòng có một cửa ra ngoài và các cửa nối với phòng kề bên. Phòng thứ $i$ cần chứa đúng $r_{i}$ con bò.

Farmer John mở khóa đúng $K$ cửa ra ngoài. Bò xếp hàng bên ngoài các cửa đã mở và lần lượt đi vào. Khi vào chuồng, mỗi con bò đi theo chiều kim đồng hồ qua các phòng cho đến khi đến phòng đích của nó.

Chi phí của mỗi con bò bằng số phòng mà nó đi qua (tính từ cửa vào đến phòng đích). Hãy chọn $K$ cửa để mở sao cho tổng chi phí đi lại của tất cả bò là nhỏ nhất.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $K$ .
$N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $r_{i}$ -- số bò cần vào phòng $i$ .

Dữ liệu ra

Một số nguyên duy nhất: tổng chi phí nhỏ nhất.

Ràng buộc

$3 \leq N \leq 1000$
$1 \leq K \leq 7$
$K \leq N$
$0 \leq r_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
6 2 2 5 4 2 6 2	14	Mở cửa phòng $2$ và phòng $5$ . Cửa phòng $2$ : bò đến phòng 2 đi $0$ bước, phòng 3 đi $1$ bước, phòng 4 đi $2$ bước -- chi phí $0 \cdot 5 + 1 \cdot 4 + 2 \cdot 2 = 8$ . Cửa phòng $5$ : bò đến phòng 5 đi $0$ bước, phòng 6 đi $1$ bước, phòng 1 đi $2$ bước -- chi phí $0 \cdot 6 + 1 \cdot 2 + 2 \cdot 2 = 6$ . Tổng $= 14$ .

Ghi chú

Mỗi cửa được mở phụ trách một đoạn liên tiếp các phòng (theo chiều kim đồng hồ). $K$ cửa chia vòng tròn thành $K$ đoạn.
Bò vào qua cửa ở đầu đoạn và đi thuận chiều kim đồng hồ đến phòng đích.

Bình luận

Không có bình luận tại thời điểm này.