P5914 [POI2004]MOS 题解

· · 题解

第一篇题解，还望通过

这道题虽然是明显的贪心题，但由于我脑袋一抽……还是不提为好。

首先分析题意。相信很多人都会每次让最快的人陪最慢的，再送火把回去（工具人？），但手算就可以发现，这种策略连样例都过不了（我就栽了好几次）。那么可以推出第二种策略：

由于第一种策略是一次送最慢的一个人先走，那么自然可以想到，可不可以让最慢的两个人送走呢？答案是肯定的。可以先让当前最快的两个过去，然后把火把送回来（最快的送），再让最慢的两个过去，火把再送来（第二快的送），两个最慢的就过去了。

结合前一种策略就可以得出公式了。


ans[i]=min(ans[i+1]+t[1]+t[i],ans[i+2]+t[1]+2*t[2]+t[i+1]);

最后再把 ans_3+t_2 输出就好了（n<=2 直接输出 a_n）。

代码如下（配注释）：

#include<bits/stdc++.h>//万能头
using namespace std;
int n;
long long t[100001],ans[100001];//不开long long见祖宗！！！
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];//只剩2个人就直接送，再加上之前的时间输出
            return 0;
        }
                ans[i]=min(ans[i+1]+t[1]+t[i],ans[i+2]+t[1]+2*t[2]+t[i+1]);
    }
    return 0;
}