P5914 [POI2004]MOS

· · 题解

题目传送门

分析

这是一道小学经典的数学题，对于这种求最短时间的题目，我们要认真考虑两组人员：

首先，跑的快的人应当跑的最多，能者多劳。

其次，跑的慢的人应当跑的最少，否则会拉慢整体的速度。

于是，本题可以用动态规划枚举到第 i 个人时候的状态。由贪心策略可以明白有以下两种方法：

  1. 让跑的最快的人做“工具人”，来回运送火把。

  2. 让跑的最快和第二快的人先过去，接下来让最快的人运送火把，最慢和第二慢的人再过去，第二快的人运送回来。

状态转移方程：dp_i=\min(a_i+a_1+dp_{i+1},a_{i+1}+2 \times a_2+a_1+dp_{i+2})

注意事项

1 十年 \text{OI} 一场空，不开 \text{long long} 见祖宗！！！

2 数组开大一些！！！

双手奉上代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[100001],c,t,cnt,dp[100001];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    if(n<=2){
        printf("%lld",a[n]);
        return 0;
    }
    dp[n]=a[n]+a[1];
    for(ll i=n-1;i>=1;--i){
        dp[i]=min(dp[i+1]+a[1]+a[i],a[i+1]+2*a[2]+a[1]+dp[i+2]);
    }
    printf("%lld",dp[3]+a[2]);
}