你有聽過有名的旅行銷售員問題嗎？問題大概可以這樣描述：給定一系列城市以及在每對城市之間移動所需要的時間，求解拜訪所有城市恰一次並且回到起始城市所需花費的最短時間。
現在你就是一位銷售員，而你的老闆需要你去每一座城市推銷商品，但你的情境跟旅行銷售員有些不同，你的情境是這樣的：
1. 你不只是需要花旅行的時間，當你在城市 i 時，你還必須要花 ti 的時間在這座城市內推銷你的商品，你一開始出發的城市也必須推銷。
2. 當你在每一座城市都推銷完商品後，你就會直接在最後一個城市下班，不用回到你出發的城市。
3. 剛出發的你活力旺盛，但是你知道長途旅行是會讓人疲累的，因此你給自己一個推銷的策略。你會先選擇一個推銷所需時間非遞減（遞增或持平）
的路線，而當你開始疲累的時候，你會轉而走向推銷所需時間非遞增（遞減或持平）的路線。舉例而言，現在有 a, b, c, d, e 五座城市，而這個順序恰好
也是你的推銷路線。假設你是在城市 c 開始感到疲倦，那麼 ta ≤ tb ≤ tc 以及 tc ≥ td ≥ te 必須成立。注意，你可以一出發就感到疲倦，或是到結束時都不感到疲倦。
4. 所有城市之間都是互相連通的，當你從城市 i 移動到城市 j 時，你所需要花的旅行時間是 tj − ti。這是一個時光可以倒流的世界，因此時間可以是負的。
你很想要趕快下班，因此你想要在最短的時間內拜訪每一座城市。你能幫自己規劃一個最好的推銷策略嗎？
輸入共有兩行，第一行是一個正整數 n ，代表城市的數量。
方便起見，每座城市都有一個 1 到 n 之間的獨特編號。
第二行有 n 個用空白分隔的非負整數，其中第 i (1 ≤ i ≤ n) 個數字 ti 代表在第 i 座城市推銷所需要的時間。 你的出發點是第 1 號城市。
1. 1 ≤ n ≤ 106
2. 0 ≤ ti ≤ 109，對於所有 1 ≤ i ≤ n
請輸出一個整數，代表你拜訪完每一座城市所需要花費的最短時間。
#test input 1: 2 100 200 #test input 2: 6 4 3 1 6 5 0 #test input 3: 10 975 187 0 7912 23 456 90 1 975 12
#test output 1: 400 #test output 2: 15 #test output 3: 9656
greedy, sortings (CF 1300)
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||