一道很有意思的貪心題，似乎noi導刊上有？記不太清了，反正是做出來了。

題意

有一個橋，一個火把，一堆人。

這對人要過橋，過橋有一些條件。

• 需要過橋的人有火把

• 不可同時過兩個以上

每次過橋的花費時間是兩人中花費最高的那位。

詢問最小的過橋花費。

注意，火把是必須有人帶回的，這個火把不能憑空傳送。

解法

這個其實并不難，我們發(fā)現(xiàn) \(n\) 為 1, 2, 3 時的都很簡單，我們從簡單處入手。

對于 \(n=1\) 略

對于 \(n=2\) 略

對于 \(n=3\) 我們讓最快的人分別帶人過去再返回送火把，答案是所有人的花費之和。

但是對于 \(n>3\) 這個并不一定是正確的策略，我們但從這一次進行考慮這個確實是最優(yōu)的，但是我們不能排除因為順序而導致的不同。

比如有兩個接近無限的數(shù)，這兩個明顯一起過更好，如果使用最快一個一個接明顯不妥當。

所以我們多了一種策略，讓最慢和次慢同行，顯然最慢和次次慢更劣。

具體來講第二種策略，我們讓最快和次快先過，最快回來送火把，最慢和次慢過去，次快回來送火把。

這兩種策略我們并不知道什么時候使用，所以直接 dp。

代碼

#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
int n, a[MN], dp[MN];
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];
	dp[n]=a[n]+a[1];
	if(n==1){
		cout<<a[1]<<'\n';
		return 0;
	}
	for(int i=n-1; i; --i)
		dp[i]=min(a[i]+a[1]+dp[i+1],a[i+1]+a[2]+a[2]+a[1]+dp[i+2]);
	cout<<dp[3]+a[2]<<'\n';
	return 0;
}