LSORTVN - LSORT
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: vdmedragon
- Nguồn bài: ONI 2005