题目：在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
输入：
两行数据：第一行为小朋友个数n
第二行有n个数，用空格隔开，分别是每个小朋友过桥的时间。
输出：
一行数据：所有小朋友过桥花费的最少时间。
样例：
输入
4
1 2 5 10
输出
17
解题思路：
我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河) 如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题) 所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }。
来看一组数据 四个人过桥花费的时间分别为 1 2 5 10
具体步骤是这样的： 第一步：1和2过去，花费时间2，然后1回来（花费时间1）； 第二歩：3和4过去，花费时间10，然后2回来（花费时间2）； 第三部：1和2过去，花费时间2，总耗时17。
代码：
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; cin>>n; int *t = new int[n]; for (int i=0;i<n;i++) { cin>>t[i]; } sort(t,t+n); vector<int> vect(n); vect[0]=0; vect[1]=t[1]; for (int i=2;i<n;i++) { vect[i] = min(vect[i-1]+t[0]+t[i],vect[i-2]+t[0]+t[i]+2*t[1]); } cout<<vect[n-1]; return 0; }
