自动搬运

查看原文

来自洛谷，原作者为

	Yanzy2333 咸鱼一条。

搬运于2025-08-24 21:43:17，当前版本为作者最后更新于2018-12-15 16:09:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这一题可以用背包的思路来做（这就是为什么这一题的标签有个背包）。

首先，设$f[\ j\ ]$表示载$j$头奶牛过河的最小时间，$sum[\ i\ ]$表示一次载$i$头奶牛过河的时间，那么状态转移方程就是：

$$f[\ j\ ]=min(f[\ j\ ],f[\ j-i\ ]+sum[\ i\ ])\text{，最后输出f[\ n\ ]} $$

这个方程是什么意思呢？

首先，$f[\ j-i\ ]+sum[\ i\ ]$就是代表少载$i$头奶牛再加上载$i$头奶牛的时间，与原来算出来的$f[\ j\ ]$比较，看一下哪一个比较少。

$i$从$1 - n$循环，$j$从$i-n$循环。

那么$sum[\ i\ ]$要怎么计算呢？我们用前缀和：

$$sum[\ i\ ]=sum[\ i-1\ ]+w[\ i\ ]\text{ (w[\ i\ ]为题目中的Mi)} $$

如果理解不来，你可以这样想：

把$i$当成完全背包的重量,$sum[\ i\ ]$当成价值，然后求最小价值。

然后每个$sum[\ i\ ]$加上$2m$，就是筏子一次来回的时间，最后输出的时候再减去$m$，因为最后一次不用划回来。

具体思路看代码：

---

#include<iostream>
#include<cstdio>
using namespace std;
int f[10010];
int sum[10010];
int w[10010];
int m,n;
const int inf=99999999;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=inf;//要求最小值的话，每一个f[i]都要赋值为无限大。
		cin>>w[i];
		sum[i]=sum[i-1]+w[i];//计算前缀和。
	}
	for(int i=1;i<=n;i++){
		sum[i]+=2*m;
	}//每个加上2*m
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			f[j]=min(f[j],f[j-i]+sum[i]);//方程，和背包差不多
		}
	}
	cout<<f[n]-m;//输出的时候减掉m，因为不用划回来。
	return 0;
}

---

题外话（如果你没时间的话，不看也没关系）：

这里附加一个$\LaTeX$公式小窍门：

在表示数组的时候，一般用

$f[i]$

$f[i]$

这样就会贴在一起，不好看。可以加一个空格（$\LaTeX$中空格是右斜杠+空格）

$f[\ i\ ]$

$f[\ i\ ]$

你还可以自行调整

$f[\,i\,]$
$f[\;i\;]$

$f[\,i\,]$

$f[\;i\;]$

当然如果你喜欢原来的样子也可以的。

或者是

$f_i$

$f_i$

---