Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LSORTVN - LSORT

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/lsortvn


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 XI, 1 <= I <=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ả XI: Khi bắt đầu thực hiện XI, 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 XI khi đó bằng K x 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 X1, X2, ..., XN.

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.

Bước	Mô tả	                P	Q	Trọng số
1	Xoá phần tử thứ 3	4 1 2	3	3
2	Xoá phần tử thứ 1	1 2	3 4	2
3	Xoá phần tử thứ 2	1	2 3 4	6
4	Xoá phần tử thứ 1	-	1 2 3 4	4

Trọng số của cách sắp xếp = 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 ≤ N ≤ 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

output 
15

Được gửi lên bởi:psetter
Ngày:2009-04-28
Thời gian chạy:0.100s-0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ONI 2005

hide comments
2009-05-04 02:50:03 dhkhtn
tuong tu LSORT(SPOJ)
2009-05-03 19:06:54 ~!(*(@*!@^&
da set lai time mot so test
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.