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

HEAP1 - Một chút về Huffman Tree

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


Một người nông dân muốn cắt 1 thanh gỗ có độ dài L của mình thành N miếng , mỗi miếng có độ dài là 1 số nguyên dương A[i] ( A[1] + A[2] + … A[N] = L ) . Tuy nhiên để cắt một miếng gỗ có độ dài là X thành 2 phần thì ông ta sẽ mất X tiền . Ông nông dân này không giỏi tính toán lắm , vì vậy bạn được yêu cầu lập trình giúp ông ta cho biết cần để dành ít nhất bao nhiêu tiền thì mới có thể cắt được tấm gỗ như mong muốn .

Lưu ý : Kết quả có thể vượt longint ( trong Pascal ) và vượt long ( trong C++ ) đấy nhé .

Input

Dòng 1 : 1 số nguyên dương T là số bộ test .
T nhóm dòng tiếp theo mô tả các bộ test , mỗi nhóm dòng gồm 2 dòng :
Dòng 1 : số nguyên dương N ( 1 ≤ N ≤ 20000 ) .
Dòng 2 : N số nguyên dương A[1] ,…, A[N] . ( 1 ≤ A[i] ≤ 50000 )

Output

Kết quả mỗi test ghi ra trên 1 dòng , ghi ra 1 số nguyên dương duy nhất là chi phí tối thiểu cần để cắt tấm gỗ .

Example

Input:
1
4
1 2 3 4

Output:
19
Đầu tiên cắt miếng gỗ thành 2 phần có độ dài 6 và 4 . Sau đó cắt tiếp miếng có độ dài 6 -> 3 và 3 . Cắt 1 miếng 3 thành 2 phần có độ dài 1 , 2 . Như vậy chi phí là 10 + 6 + 3 = 19.

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-14
Thời gian chạy:1s
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:USACO

hide comments
2023-06-23 12:00:30
r

Last edit: 2023-06-23 12:00:52
2021-05-27 18:00:55
Tham khảo: https://vnspoj.github.io/problems/HEAP1
2019-08-13 11:57:16
<(")
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1895
2019-03-29 04:38:55
- Trâu cũng ac !
2018-05-21 05:07:06
Xem thuật toán chi tiết:
http://123link.pw/AxoBwZ
2018-05-21 04:16:30
3 dòng cmm

Last edit: 2018-05-21 04:17:54
2018-05-21 03:18:09
đánh nhau pm tao nhé
2018-05-21 03:17:45
đánh nhau không
2018-05-21 03:17:08
hehe bọn gà tao AC rồi nè kakkakakakaka
2017-12-08 09:30:53
xin test case :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.