题目链接：702:Crossing River
题目大意为有n个人要过河，船最多乘两个人，给出每个人乘船时间，两人乘船时间由更慢者决定。求过河最短时间。有t组数据，输入数据组数t，对于每组数据，第一行输入总人数n，然后给出每个人乘船所需时间。输出要求每组数据单独一行，输出最短时间。
建立数学模型
首先我们建立起这道题的数学模型，两人去还要一人回来继续拉剩下的人，最快的方式无非就两种
- 最快的把最慢的拉过去，最快的回来。依次这样下去，最终只剩下两个人一起过去不再回来
- 最快的人把次快的拉过去，最快（次快）的回来，最慢和次慢一起过去，次快（最快）的再把船运回来
反正最快的和次快的在这里就是工具人，自己不过去，只是因为速度快把船运回来
因为他们都要回来，所以第一次回来和第二次回来最快和次快的顺序不用考虑
如果前面的人过河都很快，后面只有几个人要吭哧吭哧地慢慢过河，前面的人就适用于第一种办法，后面的人就适合用第二种。不能只从主观判断一定是方案1好还是方案2好，而就要靠计算机擅长于重复选择来找到最优解。
设计算法
由以上分析，我们知道了过河有两种办法，要么选1要么选2，要根据实际状况选择……听到这，你想到了什么？没错，就是动态规划！
从动态规划三要素来看，本题的三要素为：
- 阶段：题目中只有一艘船，减少了一个维度
- 状态：有多少个人需要过河就是本体的状态
- 决策：上文提到的方案1或方案2
算法实现
先要把所有人按照过河时间排一遍序，便于我们知道谁最慢谁最快
先\(f[1]=a[1], f[2]=a[2]\)，只有一个人或只有两个人时的答案是显而易见的
状态循环，从3到n循环一遍。如果选方案1，相当于多了一个人过河，找到多一个人前的状态并加上方案1所需时间，所需总时间为\(f[i-1]+a[i]+a[1]\)；如果选方案2，相当于多了两个人过河，找到多两个人之前的状态再加上方案2所需时间，所需总时间为\(f[i-2]+a[2]+a[1]+a[i]+a[2]\)
最后附上我的代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n,a[1005],f[1005];
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
f[1]=a[1];
f[2]=a[2];
for(int i=3;i<=n;i++){
f[i]=min(f[i-1]+a[i]+a[1]/*最快最慢去最快回*/,f[i-2]+a[2]+a[1]+a[i]+a[2]/*最快次快去最快回，最慢次慢去次快回*/);
}
cout<<f[n]<<endl;
}
return 0;
}