Gửi bài giải
Điểm:
0,56 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy ~P~ gồm ~N~ số hạng khác nhau từng đôi, các số hạng có giá trị trong phạm vi ~1~ ...~N~. Một cách sắp xếp dãy này thành dãy đơn điệu tăng diễn ra như sau.
- Khởi tạo danh sách ~Q =~ rỗng;
- Lần lượt thực hiện các biến đổi ~X_i~, ~1 \le i \le N~, sao cho sau dãy biến đổi này, trong danh sách ~Q~ ta nhận được dãy ~1~, ~2~, ~3~, ..., ~N~;
- Mô tả ~X_i~: Khi bắt đầu thực hiện ~X_i~, ~P~ có ~N - i + 1~ số hạng, ~Q~ có ~i - 1~ số hạng. Xoá một số hạng của ~P~, chẳng hạn số hạng thứ ~K~ và chọn việc viết tiếp số hạng đó vào bên trái hay bên phải danh sách ~Q~; Trọng số của biến đổi ~X_i~ khi đó bằng ~K \times i~;
- Trọng số của cách sắp xếp bằng tổng các trọng số của của ~N~ biến đổi ~X_1, X_2, \dots, X_N~.
Ví dụ, nếu ~P~ là dãy ~[4, 1, 3, 2]~ Bảng sau cho ta một cách sắp xếp dãy ~P~.
Trọng số của cách sắp xếp là ~15~
Cho dãy ~P~, hãy tìm một cách sắp xếp ~P~ thành dãy ~Q~ đơn điệu tăng có trọng số nhỏ nhất.
Input
- Dòng thứ nhất ghi số ~N~, ~1 \leq N \leq 1000~.
- Trong một số dòng tiếp theo ghi lần lượt ~N~ số hạng của dãy ~P~.
Output
Ghi trọng số của cách sắp xếp nhỏ nhất.
Sample Input
4
4 1
3
2
Sample Output
15
Bình luận