题目：4人过桥，ABCD要单独过桥分别需要用时1分、2分、5分、10分，桥最多只能承受2人重量，由于天黑，每次过桥时需要一个手电筒，4人中只有一个手电筒，求如何在17分钟之内全部过桥。
思路：网上搜了一下，是一个典型的贪心算法，贪心策略有两种，对应着动态规划中状态转移方程的两个状态，每次取最小时间的贪心策略就是最后的结果。
方案一：假设第i个人要过桥，由对岸最快的a[0]回来传手电筒（+a[0])，并和a[i]一起回对岸(+a[i])。
方案二：假设第i个人和第i-1个人一起过桥，因为过桥时间是取两人中的最长时间（有点像木桶的短板效应），所以过桥时间相近的人一起过桥时间损耗可能会比方案一的少，第一步仍然是由对岸最快的a[0]回来传手电筒（+a[0])，将手电筒给第i人和第i-1人，让他们一起过桥（+a[i]),然后由对岸次快的a[1]回来接a[0]重新回到对岸（+2a[i])。
容易知道3个人以下的初始最短过桥时间分别为
dp[0]=a[0]，
dp[1]=a[1],
dp[2]=a[0]+a[1]+a[2]；//a[0]和a[1]一起过桥，再由a[0]回来送手电筒，接送a[2]过桥。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll dp[10000];//前i个人过桥所需的最短时间dp[i]
ll a[10000];//a[i]为第i个人过桥所需时间
int main()
{
int n;//总共有n人需要过桥
cin >> n;
for (int i = 0;i < n;i++)
{
cin >> a[i];
}
sort(a, a + n);//对n个人过桥的时间从小到大排序
dp[0] = a[0];
dp[1] = a[1];
dp[2] = a[0] + a[1] + a[2];//三个人以下过桥的初始最短时间
for (int i = 3;i < n;i++)
{
dp[i] = min(dp[i - 1] + a[0] + a[i], dp[i - 2] + a[0] + 2*a[1] + a[i]);//方案一：假设第i个人要过桥，由对岸最快的a[0]回来传手电筒（+a[0])，并和a[i]一起回对岸(+a[i])
//方案二：假设第i个人和第i-1个人一起过桥，因为过桥时间是取两人中的最长时间（有点像木桶的短板效应），所以过桥时间相近的人一起过桥时间损耗可能会比方案一的少，第一步仍然是由对岸最快的a[0]回来传手电筒（+a[0])，将手电筒给第i人和第i-1人，让他们一起过桥（+a[i]),然后由对岸次快的a[1]回来接a[0]重新回到对岸（+2a[i])
}
cout << dp[n - 1];
}
得到的结果正好为17