P5914 [POI2004]MOS 题解

Yizhixiaoyun · 2022-04-10 21:56:56 · 题解

题目传送门

题目分析

对于本题来说，我们要考虑两个最特殊的群体。

能者多劳，当我们需要跑腿送火把时，尽量让更快的人来。
不要让慢的人拖后腿，拉慢速度。

因此本题可以考虑两种方法：

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

状态转移方程

dp_i = \min(a_i + a_1 + dp_{i+1},a_{i+1} + 2 \times a_2+a_1 + dp_{i+2})

注意事项

十年 \text{oi} 一场空，没开 \text{long long} 见祖宗。
数组要开大。
从小到大排列，所以请记得要倒着枚举。
记得特判 n = 1 的情况。

贴上代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n;
int a[maxn],dp[maxn];
inline void init(){
    cin>>n;
    for(register int i=1;i<=n;++i) cin>>a[i];
    if(n==1) cout<<a[1],exit(0);
}
int main(){
    init();
    dp[n]=a[n]+a[1];
    for(register int i=n-1;i>=1;--i) dp[i]=min(a[i]+a[1]+dp[i+1],a[i+1]+2*a[2]+a[1]+dp[i+2]);
    cout<<dp[3]+a[2];
}