nyoj 1070 诡异的电梯【Ⅰ】【dp】

谁践踏了优雅 2022-08-12 02:59 99阅读 0赞

题目：[nyoj 1070 诡异的电梯【Ⅰ】][nyoj 1070]

这个题目源自[湘潭大学oj][oj] 1206 Dormitory's Elevator

是当时比赛的题目，题目都没有读清楚啊、

分析：这其实就是一个简单的一维dp，用dp【i】表示从1层上到第 i 层花费的最小的体力。

因为不能在相邻的楼层停留，所以可以从dp【i-2】转移，但这样不是最优的还要从dp【i-3】转移，因为这样的话就可以到达所有的楼层。我们只要在所有的之间dp最优即可。

其他要注意的一个条件是，从dp【i-3】转移时，中间两层的人有四种选择：

1：都上去或都下来

2：上面的上去一层，下面的下来一层

3：上面的下来两层，下面的上去两层，（当时没有考虑到这个，要细心啊）

那么代码就很好写了、

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include <map>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int N = 100005;
    int a[N],dp[N];
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int cas=1; cas<=T; cas++)
        {
            memset(a,0,sizeof(a));
            int num,floor,up,down,x;
            scanf("%d%d%d%d",&floor,&num,&up,&down);//相反
            for(int i=1; i<=num; i++)
            {
                scanf("%d",&x);
                a[x]++;
            }
            memset(dp,0x3f3f3f3f,sizeof(dp));
            dp[0]=dp[1]=dp[2]=0;
            int tmp;
            int mi=min(up,down);
            for(int i=3; i<=floor; i++)
            {
                dp[i]=min(dp[i],dp[i-2]+a[i-1]*mi);
                if((i-3)>=1)
                {
                    tmp=min(a[i-1]*up+a[i-2]*up*2,a[i-1]*2*down+a[i-2]*down);
                    tmp=min(tmp,a[i-1]*up+a[i-2]*down);
                    tmp=min(tmp,a[i-1]*2*down+up*2*a[i-2]);
                    dp[i]=min(dp[i],dp[i-3]+tmp);
                }
            }
            printf("Case %d: %d\n",cas,dp[floor]);
        }
        return 0;
    }

[nyoj 1070]: http://acm.nyist.net/JudgeOnline/problem.php?pid=1070
[oj]: http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1206