题解 P2904 【[USACO08MAR]跨河River Crossing】
Ezio_0420
2018-01-09 18:55:38
# 玄学（蒟蒻）背包（内存优化）
## 边读入边处理加省一个数组（只需一个dp【】）
其实状态转移方程前几位也都写了，如果我们定义dp[i]为i头奶牛过河所需最短时间，定义time[i]数组为前i个奶牛过河所用的时间，那么自然得到f[j]=min(f[j],f[j-i]+time[j-i]+m)
------------
以上是正常思路，那么我们的循环是这个样子
```cpp
for (int i=1;i<=n;i++){
cin>>t;
time[i]=time[i-1]t;
}
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++){
dp[j]=min(dp[j],dp[j-i]+time[i]+m);
}
```
，接下来是蒟蒻的特色！重点来了！！（内存优化）
我们会发现，对于第二个循环中的内层循环，我们用到了time[i]来保存前i头奶牛过河时间，而此时外层循环正在枚举每一个i;所以说此时不会用到比time[i]下标大的time[]值,所以说可以把第一个循环省去；
```cpp
for (int i=1;i<=n;i++){
cin>>t;
time[i]=time[i-1]t;
for (int j=i;j<=n;j++){
dp[j]=min(dp[j],dp[j-i]+time[i]+m);
}
}
```
进一步，我们发现此时连比time[]下标小的time值都不会用到,所以说time数组完全可以省去，变为一个变量，每次加上新读入的没头奶牛的t值！
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,t,time,dp[2501];
int main(){
cin>>n>>m;
for(int i = 1;i<=n;i++) dp[i]=100000000;
time=m;
for (int i=1;i<=n;i++){
scanf("%d",&t);
time+=t;
for(int j=i;j<=n;j++){
dp[j]=min(dp[j],dp[j-i]+time+m);
}
}
cout<<dp[n]-m;
return 0;
}
一个小小的优化，希望能帮到大家
```