P5914 [POI2004]MOS 题解

V1mnkE · 2022-03-04 20:15:53 · 题解

很明显的贪心，有两种策略：

• 让最快的人和最慢的人先过去，然后让最快的人送回火把。

• 让最快和第二快的人先过去，让第一快的人送回火把，再让最慢的人和第二慢的人一起过去让第二快的人把火把送回来。

第一种就是让最慢的尽快过去，第二种是让两个最慢的尽快过去。

温馨提示：十年oi一场空，不开 long long 见祖宗。

状态转移方程：ans_i= \min (ans_{i+1}+t_1+t_i, ans_{i+2}+t_1+t_2\times 2 +t_{i+1})

由于是从小到大排列，所以我们要倒着枚举。

代码

#include<bits/stdc++.h>
using namespace std;
int t[100005],ans[100005],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>t[i];
    ans[n]=t[n]+t[1];
    for(int i=n-1;;i--){
        if(i<=2)cout<<ans[3]+t[i],exit(0);
        ans[i]=min(ans[i+1]+t[1]+t[i],ans[i+2]+t[1]+2*t[2]+t[i+1]);
    }
    return 0;
}