题解 P2904 【[USACO08MAR]跨河River Crossing】
Yanzy2333
·
·
题解
这一题可以用背包的思路来做（这就是为什么这一题的标签有个背包）。
首先，设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\ ]比较，看一下哪一个比较少。
那么$sum[\ i\ ]$要怎么计算呢？我们用前缀和：
$$sum[\ i\ ]=sum[\ i-1\ ]+w[\ i\ ]\text{ (w[\ i\ ]为题目中的Mi)}$$
如果理解不来，你可以这样想：
把$i$当成完全背包的重量,$sum[\ i\ ]$当成价值，然后求最小价值。
然后每个$sum[\ i\ ]$加上$2m$，就是筏子一次来回的时间，最后输出的时候再减去$m$，因为最后一次不用划回来。
具体思路看代码：
---
```cpp
#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$
---