迁徙过程中的河流

解题思路

有 N 个人需要渡河，有一条船，船上最多只能乘坐两人。第 i 个人一个人划船到对面需要 T[i-1] 时间。
为了保证船的平衡，当船上有两人时，需按照慢的那个人的速度划船，也就是说船到达对岸的时间等于船上渡河时间长的那个人的时间。
求所有人过河的花费时间最少为多少？

首先将 N 个人按照渡河时间从小到大排序，则第 1 个人和第 2 个人可以作为来回划船的人。

dp[i] 表示前 i+1 个人过河花费的最少的总时间。
dp[0] = T[0]，表示1 个人过河时间。
dp[1] = T[1]，两个人一起划到对岸。
dp[i] = min(dp[i-1]+T[0]+T[i], dp[i-2]+T[0]+T[i]+T[1]+T[1])。
前 i 个人渡河时间为 dp[i-1]，还有 1 人需要渡河，由第 1 个人花费 T[0] 时间接第 i+1 个人，两人渡河时间为 T[i]。
此时，dp[i] = dp[i-1] + T[0] + T[i]。
前 i-1 个人渡河时间为 dp[i-2]，还有两个人需要渡河，由第 1 个人花费 T[0] 时间划船回来，第 i 个人和第 i+1 个人一起过河花费时间为 T[i]，再由第 2 个人将船划回来，时间为 T[1]，和第 1 个人一起渡河，时间为 T[1]。
此时，dp[i] = dp[i-2] + T[0] + T[i] + T[1] + T[1]。
取两种方案的较小值。最后 dp[n-1] 是结果。

C++代码

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    vector<int> T(N);
    for(int i=0; i<N; ++i){
        scanf("%d", &T[i]);
    }
    sort(T.begin(), T.end());
    vector<int> dp(N, 0);
    dp[0] = T[0];
    dp[1] = T[1];
    for(int i=2; i<N; ++i){
        dp[i] = min(dp[i-1]+T[0]+T[i], dp[i-2]+T[0]+T[i]+T[1]+T[1]);
    }
    printf("%d\n", dp[N-1]);
    return 0;
}