Đồi

Điểm: 6,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

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho dãy $n$ ngọn đồi với chiều cao lần lượt là $a_{1}, a_{2}, \dots, a_{n}$ . Người ta muốn xây nhà trên một số ngọn đồi, nhưng để đảm bảo mỹ quan, một ngôi nhà chỉ có thể đặt trên ngọn đồi cao hơn nghiêm ngặt cả hai ngọn đồi kề (nếu có).

Ví dụ với dãy chiều cao $5, 4, 6, 2$ thì chỉ có thể xây nhà trên ngọn đồi chiều cao $5$ và ngọn đồi chiều cao $6$ .

Có một chiếc máy xúc có thể giảm chiều cao của một ngọn đồi tuỳ ý đi $1$ đơn vị trong $1$ giờ làm việc. Máy xúc chỉ làm việc trên một ngọn đồi tại một thời điểm. Chiều cao có thể giảm xuống $0$ hoặc thậm chí âm. Không thể tăng chiều cao bất kỳ ngọn đồi nào.

Với mỗi $k$ từ $1$ đến $⌈ n / 2 ⌉$ , hãy tính số giờ tối thiểu cần thiết để san phẳng các ngọn đồi sao cho có ít nhất $k$ ngọn đồi đủ điều kiện xây nhà.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — số ngọn đồi.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — chiều cao các ngọn đồi.

Dữ liệu ra

In ra đúng $⌈ n / 2 ⌉$ số nguyên trên một dòng, cách nhau bởi dấu cách. Số thứ $i$ là số giờ tối thiểu để có thể xây được ít nhất $i$ ngôi nhà.

Ràng buộc

$1 \leq n \leq 5000$
$1 \leq a_{i} \leq 100 000$

Ví dụ

Input	Output	Giải thích
5 1 2 3 2 2	0 1 3	Với $k = 1$ : ngọn đồi $3$ đã thoả mãn, cần $0$ giờ. Với $k = 2$ : giảm $a_{4}$ xuống $1$ , khi đó các ngọn đồi $3$ và $5$ đều cao hơn các ngọn đồi kề, mất $1$ giờ. Với $k = 3$ : mất $3$ giờ.
3 1 2 3	0 2	Với $k = 1$ : ngọn đồi $3$ đã cao nhất, không cần giảm. Với $k = 2$ : cần giảm $a_{2}$ xuống $0$ , mất $2$ giờ; khi đó ngọn đồi $1$ và $3$ đều thoả mãn.
5 1 1 1 1 1	1 2 2	Với $k = 1$ : giảm $a_{2}$ xuống $0$ để ngọn đồi $1$ thoả mãn, mất $1$ giờ. Với $k = 2$ : giảm $a_{2}$ và $a_{4}$ để ngọn đồi $1, 3$ thoả mãn, mất $2$ giờ. Với $k = 3$ : giảm $a_{2}, a_{4}$ để ngọn đồi $1, 3, 5$ đều thoả mãn, vẫn mất $2$ giờ.

Bình luận

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