题目描述：
在一个夜黑风高的晚上，有 nn 个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不超过两人通过，他们只有一个手电筒，所以每次过桥后，需要有人把手电筒带回来，第 ii 号小朋友过桥的时间为 a_iai，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。 输入格式 第一行输入一个整数 nn，表示有 nn 个小朋友。 第二行有 nn 个整数 a_iai ，a_iai 表示第 ii 个小朋友过河需要的时间。 输出格式 输出一个整数，表示所有小朋友过河所需要的最短时间。
解题思路： 我们定义dp[i]：代表一共有i个人的话，需要花费的最少时间。 首先给数组升序（其中，a[1]是数组的第一个元素），假设现在一共有i个人，那么可以分为两种情况： （1）没有过河的人是第i-1个人，和第i个人两个人【已经有i-2个人已经过河了】：dp[i]=dp[i-2]+a[1]+a[i]+2*a[2]；（在dp[i-2]的基础之上，加上第一个人回来送手电筒的时间【a[1]】+第i-1和第i个人拿着手电筒过河的时间【a[i]】+第2个人回去送手电筒【a[1]】+第1个人和第2个人一起过河的时间【a[2]】） （2）没有过河的人是第i个人【已经有i-1个人已经过河了】：dp[i]=dp[i-1]+a[1]+a[i]；（在dp[i-1]的基础之上，加上第一个人回来送手电筒的时间【a[1]】+第1个人和第i个人一起过河的时间【a[i]】）
AC代码：
//过河 #include <stdlib.h> #include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> #include <math.h> #define min(a,b) a<b?a:b; using namespace std; int a[1010]; int dp[1010]; int main() { int n,i; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); //dp[i]：代表一共有i个人的话，需要花费的最少时间 dp[1]=a[1]; dp[2]=a[2]; dp[3]=a[1]+a[2]+a[3]; for(i=4;i<=n;i++) { dp[i]=min(dp[i-1]+a[1]+a[i],dp[i-2]+a[1]+a[i]+2*a[2]); } cout<<dp[n]<<endl; return 0; }