P5914 [POI2004]MOS 题解

JAMES__KING · 2022-08-28 10:43:08 · 题解

题目传送门

题目分析

1.首先考虑让走得最快的人来回送火把，依次把第二快、第三快的人送过去，最后再把走得最慢的人送到对岸。可是模拟了样例，却发现连样例也过不了，于是考虑第二种方法。

2.通过推导样例可以知道，此题有两种最佳策略：

• 当我们需要送火把时，让对岸走得最快的人来。
• 不要让走得慢的人拖后腿，让速度变慢。

3.根据以上的最佳策略可得出两种方法：

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

坑点：

1. 数组、数据要开大。
2. 从小到大排列，所以请记得要倒着枚举。

根据上述方法，便可以完成代码了。

慷慨的亮出代码：

#include<bits/stdc++.h>
using namespace std;
long long a[100005],f[100005],n;
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++) cin>>a[i];
    f[n]=a[1]+a[n];
    for(long long i=n-1;i>=1;i--)//从大到小枚举
        f[i]=min(a[i]+a[1]+f[i+1],a[i+1]+a[1]+a[2]*2+f[i+2]);//状态转移方程
    cout<<f[3]+a[2];
    return 0;
}