题解 P2904 【[USACO08MAR]跨河River Crossing】

· · 题解

题目描述

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一个人把木筏从对岸划回来接下一批的奶牛的时间。

首先，我们可以定义dp[i]表示把i头牛送到对岸的最短时间。

我们可以枚举最后一次运到对岸的有几头牛，设为j，然后dp方程就很好列了：

dp[i] = min(dp[i], dp[j] + s[j] + 2 * m)

s[j]为m[1..j]的和，即j头牛的总时间，s[j]加上FJ的时间m是划到对岸的总时间，再加上的m是FJ回来的时间。

下面上代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2510;
int dp[maxn], s[maxn];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i=1, x; i<=n; ++i) {
        scanf("%d", &x); 
        s[i]=s[i-1]+x; //计算出s[i]
    }
    memset(dp, 0x7f, sizeof(dp)); //一开始无限大
    dp[0]=0; //0头牛需要的时间肯定是0
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=i; ++j) 
            dp[i]=min(dp[i], dp[i-j]+s[j]+2*m);
    printf("%d", dp[n]-m); //最后要减去m是因为最后一次划船不需要回来
    return 0;
}