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(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	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]);
	}
	cout<<dp[3]+a[2];
}