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

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)


以上是正常思路,那么我们的循环是这个样子

    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[]值,所以说可以把第一个循环省去;

    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值!

    #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;
    }
一个小小的优化,希望能帮到大家