1719 測資加強 已 rejudge
1362 . 工程發包問題
Description
「合眾國日本」政府準備興建一條從長崎直接通往中華聯邦的海底鐵路，
這個大工程其實是可以分成N項花費時間都是1的基礎小工程來做的，
每一間公司只能做一件事情，看是要處理一項工程，
或者是將他負責的所有工程發包給兩家公司之後進行監督。
工程全部結束後監督公司必須負責檢查。
如果監督公司上面還有監督公司，那麼上面的監督公司還要在檢查一遍，依此類推。
一間公司在同一時間只能興建或檢查一樣工程，
但時同一時間可能有很多公司在進行建造或檢查工作。
給你這些工程的資料，你能夠算出最少要花費多少時間才能完成嗎？
Input Format
第一行有一個整數N代表有幾件工程，(N<=250)
接下來有N行，每行一個數字代表一項工程的檢查所需時間。
Output Format
請輸出最少要花費多少時間才能完成工作。
Sample Input 1
3
1
2
3
1
2
3
Sample Output 1
10
Sample Input 2
4
1
2
3
4
1
2
3
4
Sample Output 2
16
Hints
 |  |
| 第一組測資有三個工程，監督所需時間分別是1、2、3。 最佳的分配方法如圖所示。 A公司將工程1、2分配給B公司，而工程3分給C公司。 B公司又分別將工程分給D公司跟E公司。 所以當D公司跟E公司花費1的時間做完後，B公司花3的時間檢查。 B檢查完後又由A檢查全部的三個工程，又花費6的時間。 所以一直到時間10全部的工作才做完。(10=6+3+1) | 自己看著辦吧 ;) |
※2008/07/10 補上範例測資說明 by akira。
Problem Source
原TIOJ1362 / 快樂暑假營第一次練習比賽。Problem Setter：akira
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |