2020年牛客算法入门课练习赛2 C-迁徙过程中的河流

题目链接

https://ac.nowcoder.com/acm/contest/5968/C

思路

典型的过桥问题.

有N（N≥2）个人在晚上需要从X地到达Y地，中间要过一座桥，过桥需要手电筒（而他们只有1个手电筒），每次最多两个人一起过桥（否则桥会垮）。N个人的过桥时间依次存入数组t[N]中，分别为：t[0], t[1], ……, t[N-1]。过桥的速度以慢的人为准！注意：手电筒不能丢过桥！问题是：编程求这N个人过桥所花的最短时间。

过桥问题的解法是贪心。我们先考虑三个人的情况。
很显然如果只有三个人，假设从快到慢分别是a,b,c。a先将b送过桥，再返回将c送过桥，总花费是(T_a+T_b+T_c)
如果有四个人，假设从快到慢分别是a,b,c,d。d过桥的时间一定只能算一次，否则一定不是最优解。所以我们可以将问题转化为谁把d送过来。
根据贪心的原则，我们一定不希望c贡献答案，所以我们的希望是a,b过桥，a返回c,d过桥，b返回a,b过桥，总花费是(T_b+T_a+T_d+T_b+T_b=T_a+3*T_b+T_d)
以上两个例子不难发现贪心策略有两种，一种是最快的a将最慢的送过桥，一种是最快的返回最慢和次慢的过桥，次快过桥接最快回去。
设最快、次快、次慢、最慢的时间分别为a[1],a[2],a[n-1],a[n]，
第一个策略的花费就是(a[1]+a[n])，
第二个策略的花费就是(a[1]+a[n]+a[2]*2)
dp[i]表示前i个人都过桥的最优解，(dp[i]=min(dp[i-1]+a[i]+a[1],dp[i-2]+a[1]+a[i]+a[2]*2))

代码

#include<bits/stdc++.h>
#define long long ll;
using namespace std;
int a[100005];
int dp[10005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    dp[1]=a[1];
    dp[2]=a[2];
    for(int i=3;i<=n;i++){
        dp[i]=min(dp[i-1]+a[i]+a[1],dp[i-2]+a[1]+a[i]+a[2]*2);
    }
    cout<<dp[n]<<endl;
    return 0;
}