nyoj 1070 기괴한 엘리베이터[I][dp]

제목:니오제이 1070 기괴한 엘리베이터[I]
이 제목은 상담대학교 oj1206 Dormitory's Elevator에서 유래한 것입니다.
당시 시합 제목인데 제목도 제대로 못 읽었는데,
분석: 이것은 사실 간단한 1차원 dp로 dp[i]로 1층에서 i층까지 소비하는 가장 적은 체력을 나타낸다.
인접한 층에 머물 수 없기 때문에 dp[i-2]에서 옮길 수 있지만 이것은 가장 좋은 것이 아니라 dp[i-3]에서 옮길 수 있기 때문에 모든 층에 도달할 수 있다.우리는 모든 것 사이에서 dp가 가장 우수하기만 하면 된다.
기타 주의해야 할 조건 중 하나는 dp[i-3]에서 이동할 때 중간 두 층의 사람들은 네 가지 선택을 할 수 있다는 것이다.
1:올라가든지 내려오든지
2:위쪽은 위쪽, 아래쪽은 아래쪽.
3:위쪽은 아래쪽 2층, 아래쪽은 위쪽 2층.
그럼 코드는 잘 쓰이고,
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
",cas,dp[floor]); } return 0; }

좋은 웹페이지 즐겨찾기