【题解】「USACO2008MAR」River Crossing（DP）

本文主要是介绍【题解】「USACO2008MAR」River Crossing（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
$Farmer$ $John$以及他的$N(1<=N<=2,500)$头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。
由于奶牛不会划船，在整个渡河过程中，$FJ$必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加$1$，$FJ$把木筏划到对岸就得花更多的时间。 当$FJ$一个人坐在木筏上，他把木筏划到对岸需要$M(1<=M<=1000)$分钟。当木筏搭载的奶牛数目从$i-1$增加到$i$时，$FJ$得多花$M_i(1<=M_i<=1000)$分钟才能把木筏划过河（也就是说，船上有$1$头奶牛时，$FJ$得花$M+M_1$分钟渡河；船上有$2$头奶牛时，时间就变成$M+M_1+M_2$分钟。后面的依此类推）。那么，$FJ$最少要花多少时间，才能把所有奶牛带到对岸呢？当然，这个时间得包括$FJ$一个人把木筏从对岸划回来接下一批的奶牛的时间。
【输入】
第一行两个整数数$N,M$，表示$N$头奶牛和$FJ$独自划到对岸的时间；
接下来$N$个数，为$M_i$
【输出】
一个整数，最少时间。
【样例输入】

5 10 
3 
4 
6 
100 
1

【样例输出】

50

【样例解释】
$FJ$第一次带$3$头牛过河，一共花费$10+3+4+6=23$分钟，然后一个人划回来，花费$10$分钟，最后带剩下的$2$头牛过河，花费$10+3+4=17$分钟，总共$23+10+17=50$分钟。

算法分析

对于$DP$，最简单的状态就是问题怎么问，怎么设。
状态：
$f[i]$——运输$i$头牛过河花费的最少时间。

状态转移方程：
总共运输$i$头牛，考虑当前这一次运输了几头牛，设当前这一次运输$j$头牛。数组$sum$存放$M_i$.
$f[i]=min${ $f[i-j]+sum[j]+2\ast m$ }，$1<=i<=n,1<=j<=i。$

最后的答案就是$f[n]-m$（$FJ$运输最后一次不会返回）。
时间复杂度：$O(n^2)$

参考程序

#include<iostream>
#include<cstring> 
#include<cstdio> 
#define N 3000 
using namespace std;
int f[N],sum[N];
int main()
{int n,m;cin>>n>>m;int a;for(int i=1;i<=n;i++){cin>>a;sum[i]=sum[i-1]+a;}for(int i=1;i<=n;i++){int minn=N*10000;for(int j=1;j<=i;j++)	//当前这一次运输j头牛minn=min(minn,f[i-j]+sum[j]+2*m);f[i]=minn;}cout<<f[n]-m<<endl;     //送完了就不用会来了 return 0;
}

这篇关于【题解】「USACO2008MAR」River Crossing（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---