題目連結：
題目大意：
有一群人要過橋，而每個人過橋的速度不同。只有一盞燈，必須滿足下列條件：
１．一次最多只能過兩個人，必須要有一個人拿燈往返橋的兩邊
２．當一人過橋時，過橋的速度就是自己原來的速度
３．當兩個人過橋時，速度快的人必須遷就速度慢的人，所以兩個人過橋的時間等於較慢的人之速度
現在第一列給定一正整數 ｍ （１ ≦ ｍ ≦ ３０），代表有 ｍ 個人要過橋。第二列則給定 ｍ 個正整數（皆介於 １ ～ １, ０００之間）代表這 ｍ 個人過橋所需要的時間。
求這 ｍ 個人都過去橋的另一段所需要花的最短時間為何？
範例輸入：
5
11 7 4 2 1
4
5 5 3 1
0
範例輸出：
23
15
解題思維：
假設現在還沒過橋的有 ｋ 個人，每個人過橋所需的時間由小到大排好為 Ｔ１ 、 Ｔ２ 、 …… 、 Ｔｋ－１ 、 Ｔｋ 。
則只要當前情況滿足 ｋ ≧ ４ 且 Ｔｋ－１ ＋ Ｔ１ ＞ ２ × Ｔ２ ，就把第一快的人、第二快的人一起送過去，然後讓第一快的人回來。然後最慢、第二慢的人一起過去，再讓第二快的人回來。所以總共的時間多了 Ｔ１ ＋ ２ × Ｔ２ ＋ Ｔｋ ，且必定是最佳的方法。
如果不滿足上面的情況，則讓第一快跟最慢的人一起過去，最快的人再回來。因此所耗時間要加上 Ｔｋ ＋ Ｔ１。
以上情形做到剩最後一個人時（剩最快的人），所求即是此人的時間 ＋ 前面耗掉的時間。
至於判斷式 Ｔｋ－１ ＋ Ｔ１ ＞ ２ × Ｔ２ 的由來為以下：
我們可以看到上面兩個情況要把最慢的兩個人送到橋對面的耗時分別為：
Ｔ１ ＋ ２ × Ｔ２ ＋ Ｔｋ （上面的情況）
２ × Ｔ１ ＋ Ｔｋ ＋ Ｔｋ－１ （下面的情況）
因為要盡量把最慢的人送過去，然後讓要往返的人盡量是最快的。因此只有這兩個情況是最佳的。而當：
Ｔ１ ＋ ２ × Ｔ２ ＋ Ｔｋ ＞ ２ × Ｔ１ ＋ Ｔｋ ＋ Ｔｋ－１
時，上面的作法最佳。簡化上式即變為：
Ｔｋ－１ ＋ Ｔ１ ＞ ２ × Ｔ２
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
