题解 P2904 【[USACO08MAR]River Crossing S】

· · 题解

update:新增代码注释和完整代码，并修正一些表述。

如果代码缩进奇怪，请以博客界面为准。

本题并不是传统意义上的背包，但用到了背包思想。

观察样例可知，运送i头奶牛过河要加上前几头奶牛的时间一起，所以我们可以前缀和预处理一下。

代码如下

//此处m数组用来存储FJ+i头奶牛过河的时间
scanf("%d%d",&n,&m[0]);//FJ一个人过河的时间为m[0]（0头牛）
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&m[i]);
        m[i]+=m[i-1];//前缀和
    }

接下来就是核心的背包部分了，我们设f[i]表示FJ送i头奶牛过河的最短时间。因为本题的特殊性，我们可以直接用刚才的m数组作为DP数组使用。

我们把i头奶牛分成两批（why？因为没必要分那么多，效果是一样的）送，for循环会一直细分到最小的两批的情况。

因为FJ还要回来，所以分成两批送的时间要加上FJ回来的过河时间。

具体请详见代码理解

for(int i=1;i<=n;i++)//FJ送i头奶牛过河的最短时间
        for(int j=1;j<i/*题目保证奶牛数量大于0*/;j++) m[i]=min(m[i],m[j]+m[i-j]+m[0]);//两批，加FJ回来的时间
    printf("%d",m[n]);//输出最终结果

无注释版（注释见上）完整代码感觉不放也行

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m[2510];
int main()
{
//  freopen("work.in","r",stdin);freopen("work.out","w",stdout);
    scanf("%d%d",&n,&m[0]);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&m[i]);
        m[i]+=m[i-1];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++) m[i]=min(m[i],m[j]+m[i-j]+m[0]);
    printf("%d",m[n]);
//  fclose(stdin);fclose(stdout);
    return 0;
}

是不是很简洁呀233，求各位评价一下马蜂。

Thank you for your watching!