Chia Mảng Knuth

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Cho mảng $n$ số nguyên. Ban đầu cả mảng là một đoạn duy nhất. Mỗi bước, bạn chọn một đoạn và chia nó thành hai đoạn liên tiếp. Chi phí của một lần chia đoạn bằng tổng tất cả các phần tử trong đoạn đó. Mục tiêu là chia mảng thành $n$ đoạn đơn (mỗi đoạn gồm một phần tử) với tổng chi phí nhỏ nhất.

Dữ liệu vào

Dòng 1: số nguyên $n$ .
Dòng 2: $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .

Dữ liệu ra

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

Ràng buộc

$1 \leq n \leq 5000$
$1 \leq x_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 2 7 3 2 5	43	Chia [2,7,3,2,5] (tổng 19) tại vị trí 2: chi phí 19. Được [2,7] và [3,2,5]. Chia [2,7] (tổng 9): chi phí 9. Chia [3,2,5] tại 2 (tổng 10): chi phí 10. Chia [2,5] (tổng 7): chi phí 7. Tổng = 19+9+10+7 = 45. Tối ưu hơn: chia khác → 43.
1 5	0	Chỉ một phần tử, không cần chia.

Bình luận

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