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.|

NRS - Xếp toa

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/nrs


Một công ty vận tải thuê 1 đoàn tàu hỏa để chở hàng cho khách. Tuy nhiên sau khi đã xếp hàng lên hết thì nhận được thêm yêu cầu từ khách là hàng phải được xếp sao cho toa nặng phải ở phía trước toa nhẹ, nói cách khác là các toa phải được sắp xếp theo vị trí giảm dần về trọng lượng hàng hóa trong toa.

Các toa đã được niêm phong nên không thể chuyển hàng giữa các toa được. Cách duy nhất là yêu cầu nhà ga dùng 1 chiếc cần cẩu để chuyển vị trí các toa. Vị trí các toa được đánh số từ 1 trở đi, bắt đầu từ toa phía trước nhất.

Khi cần cẩu chuyển toa từ vị trí I sang vị trí J, vị trí sắp xếp tương đối giữa các toa còn lại không bị thay đổi. Nếu I > J thì số thứ tự vị trí của các toa giữa J và I-1 sẽ tăng thêm 1. Ngược lại, nếu I < J thì số thứ tự vị trí của các toa giữa I+1 và J sẽ giảm đi 1. Chi phí cho mỗi lần cẩu toa I sang vị trí J là I+J đơn vị giá.

Nhiệm vụ của bạn là tìm cách chuyển hàng sao cho tổng số chi phí là thấp nhất.

Dữ liệu

Dòng đầu tiên gồm 1 số nguyên dương N (2 ≤ N ≤ 1000) là số lượng toa đã được dùng để xếp hàng. Trong N dòng tiếp theo, mỗi dòng gồm 1 số nguyên Si (0 ≤ Si ≤ 1000000) là trọng lượng của toa hàng tương ứng theo thứ tự từ 1 đến N.

Giới hạn: 30%Test có N ≤ 10

Kết quả

Một dòng duy nhất ghi tổng chi phí nhỏ nhất để chuyển các toa theo vị trí yêu cầu của khác hàng.

Ví dụ

Dữ liệu:
5
15
40
1
8
6

Kết quả:
11


Được gửi lên bởi:Race with time
Ngày:2008-07-21
Thời gian chạy: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:Adrian Kuegel

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.