自动搬运

查看原文

来自洛谷，原作者为

	wzxx AFO（找女朋友加q：1420991849）

搬运于2025-08-24 21:48:35，当前版本为作者最后更新于2017-12-31 18:03:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

动态规划（两个版本）

先分析一下题目。

1. 所有城市连起来是一条链。

2. 每一天有走和不走两种选择。

仅凭这两点，我们就很容易想到dp的思路。我写了两个版本，一个是龟速版，总用时2000多ms；一个是飞速版，总用时8ms......

先说说龟速的把。设状态f[i][j]表示第j天 到达 第i个城市的最小疲劳值，也就是说这一天你必须是刚好从前一个城市走到这里来的。状态转移方程就很容易推出来了，就是找上一个城市在i-1..j-1天里哪天到达的疲劳值最小，然后再加上这一天从上一个城市到达这一个城市的疲劳值。为什么是i-1..j-1而不是1..j-1呢？因为第i-1个城市最早只能在第i-1天到达，继续找前面的完全就没有必要。想一想，第3个城市能在第2天到达吗？当然不行。

上述文字用公式表达就是这个样子：

f[i][j]=min{f[i-1][i-1..j-1]}+D[i]\*C[j]

为什么这个公式就可以成立呢？因为你找到了哪一天到达上一个城市的疲劳值最小，你就可以不停地休息（休息是不会增加疲劳值的），一直休息到第j天，再走过来，这样就是最优的了。

代码：

    #include<iostream>
    #include<cstdio>
    #include<fstream>
    #include<algorithm>
    #include<string>
    #include<sstream>
    #include<cstring>
        using namespace std;
        const int INF=2139063143;
        int D[1002],C[1002],f[1002][1002];
    int main()
    {
        memset(f,0x7f,sizeof(f));
        int N=0,M=0;
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++) scanf("%d",&D[i]);
        for(int i=1;i<=M;i++) 
        {
            scanf("%d",&C[i]);
            f[1][i]=D[1]*C[i];//初始化第一个城市的
        }
        for(int i=2;i<=N;i++)
            for(int j=i;j<=M;j++)
            {
                int Min=INF;
                //找最小
                for(int k=j-1;k>=i-1;k--) Min=min(Min,f[i-1][k]);
                f[i][j]=Min+D[i]*C[j];//更新
            }
        int ans=INF;
        for(int i=N;i<=M;i++) ans=min(ans,f[N][i]);
        printf("%d",ans); 
        return 0;
    }

接着再说一下快速的吧。设状态f[i][j]表示第j天 位于 第i个城市的最小疲劳值，也就是说这一天你可以不是刚好从前一个城市走到这里来的，也可以是前几天已经到了，休息到今天的。再看题目，对于每一天都有走和不走两种选择，状态转移方程就出来了。对于在第i个城市的第j天，你可以在j-1天从上一个城市走过来（第1种选择），也可以休息不走（第2种选择）。这里和龟速版的意思一样，也是看一看从上一个城市的哪一天走过来最优，只不过可以休息。

上述文字用公式表达就是这样子：

f[i][j]=min{f[i][j-1],f[i-1][j-1]+D[i]\*C[j]}

其中f[i][j-1]是休息，f[i-1][j-1]+D[i]*C[j]是走。

代码：

    #include<iostream>
    #include<cstdio>
    #include<fstream>
    #include<algorithm>
    #include<string>
    #include<sstream>
    #include<cstring>
        using namespace std;
        const int INF=2139063143;
        int D[1002],C[1002],f[1002][1002];
    int main()
    {
        int N=0,M=0;
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;i++) scanf("%d",&D[i]);
        for(int i=1;i<=M;i++) scanf("%d",&C[i]); 
        memset(f,0x7f,sizeof(f));
        for(int i=0;i<=M;i++) f[0][i]=0;
        for(int i=1;i<=N;i++)
            for(int j=i;j<=M;j++)
                f[i][j]=min(f[i][j-1],f[i-1][j-1]+D[i]*C[j]);
        int ans=INF;
        for(int i=N;i<=M;i++) ans=min(ans,f[N][i]);
        printf("%d",ans); 
        return 0;
    }

两种方案，个人感觉第一种好理解一点，但速度真的超级慢啊，大家自行取舍吧。