首页 > 代码库 > 舞蹈家怀特先生

舞蹈家怀特先生

codevs 3049 舞蹈家怀特先生

http://codevs.cn/problem/3049/

难度等级:黄金

题目描述 Description

怀特先生是一个大胖子。他很喜欢玩跳舞机(Dance Dance Revolution, DDR),甚至希望有一天人家会脚踏“舞蹈家怀特先生”。可惜现在他的动作根本不能称作是在跳舞,尽管每次他都十分投入的表演。这也难怪,有他这样的体型,玩跳舞机是相当费劲的。因此,他希望写一个程序来安排舞步,让他跳起来轻松一些,至少不要每次都汗流浃背。
  DDR的主要内容是用脚来踩踏板。踏板有四个方向的箭头,用1 (Up)、2 (Left)、3 (Down)、4 (Right)来代表,中间位置由0来代表。每首歌曲有一个箭头序列,游戏者必须按照或这个序列一次用某一只脚踩相应的踏板。在任何时候,两只脚都不能在同一踏板上,但可以同时待在中心位置0。
  每一个时刻,它必须移动而且只能移动他的一只脚去踩相应的箭头,而另一只脚不许移动。跳完一首曲子之后,怀特先生会计算他所消耗的体力。从中心移动到任何一个箭头耗费2单位体力,从任何一个箭头移动到相邻箭头耗费3单位体力,移动到相对的箭头(1和3相对,2和4相对)耗费4单位体力,而留在原地再踩一下只需要1单位。怀特先生应该怎样移动他的双脚(即,对于每个箭头,选一只脚去踩它),才能用最少的体力完成一首给定的舞曲呢?
  例如,对于箭头序列Left (2), Left (2), Up (1), Right (4),他应该分别用左、左、右、右脚去踩,总的体力耗费为2+1+2+3=8单位。

输入描述 Input Description

第一行N,表示有N个时刻 1<=N<=10000
第二到n+1行,每行一个数,表示需要踩得版

输出描述 Output Description

一个数,最小消耗体力

样例输入 Sample Input

2

1

1

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

n<=10000

f[i][l][r]表示踩了i步,第i步左脚踩在l,右脚踩在r的最小消耗体力

初始化:f极大值

特殊处理:第1步规定左脚踩,左脚踩到直到出现与第一个不同的箭头,换右脚踩第一步

状态转移:设第i步踩在x

f[i][l][r]=min(f[i-1][x][r]+move[l][x])

f[i][l][r]=min(f[i-1][l][r]+move[r][x])

第一次代码,没有预处理move数组,代码冗长,判断移动消耗多少体力时老出错

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,f[10001][5][5],y,ans=50000;
int work(int i,int l,int r,int self,int left,int right,int now_l,int now_r,int p)
{
    if(p==self) f[i][now_l][now_r]=min(f[i][now_l][now_r],f[i-1][l][r]+1);
    else if(p==left||p==right)  f[i][now_l][now_r]=min(f[i][now_l][now_r],f[i-1][l][r]+3);
    else f[i][now_l][now_r]=min(f[i][now_l][now_r],f[i-1][l][r]+4);
}
int main()
{
    scanf("%d",&n);
    memset(f,127,sizeof(f));
    f[0][0][0]=0;
    int a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y); 
        if(i==1)
        {
            f[1][y][0]=2,a=y;
            continue;
        }
        if(a)
        {
            if(y==a)
             f[i][y][0]=f[i-1][y][0]+1;
            else
             {
                 f[i][a][y]=f[i-1][a][0]+2;
                 a=0;
             }
             continue;
        }
        for(int l=1;l<=4;l++)
         for(int r=1;r<=4;r++)
         {
             if(f[i-1][l][r]>40000) continue;
             if(y==1)  work(i,l,r,1,2,4,y,r,l);
             else if(y==2) work(i,l,r,2,1,3,y,r,l);
             else if(y==3) work(i,l,r,3,2,4,y,r,l);
             else  work(i,l,r,4,1,3,y,r,l);
         }
        for(int l=1;l<=4;l++)
         for(int r=1;r<=4;r++)
         {
             if(f[i-1][l][r]>40000) continue;
             if(y==1)  work(i,l,r,1,2,4,l,y,r);
             else if(y==2) work(i,l,r,2,1,3,l,y,r);
             else if(y==3) work(i,l,r,3,2,4,l,y,r);
             else  work(i,l,r,4,1,3,l,y,r);
         }
    }
    for(int i=0;i<=4;i++)
     for(int j=0;j<=4;j++)
      ans=min(ans,f[n][i][j]);
    printf("%d",ans);
}

第二次代码,预处理move数组,简单方便

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,f[10001][5][5],y,ans=50000;
int move[5][5]={{0,2,2,2,2},{0,1,3,4,3},{0,3,1,3,4},{0,4,3,1,3},{0,3,4,3,1}};
int main()
{
    scanf("%d",&n);
    memset(f,127,sizeof(f));
    f[0][0][0]=0;
    int a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y); 
        if(i==1)
        {
            f[1][y][0]=2,a=y;
            continue;
        }
        if(a)
        {
            if(y==a)
             f[i][y][0]=f[i-1][y][0]+1;
            else
             {
                 f[i][a][y]=f[i-1][a][0]+2;
                 a=0;
             }
             continue;
        }
        for(int l=1;l<=4;l++)
         for(int r=1;r<=4;r++)
         {
             if(f[i-1][l][r]>40000) continue;
            f[i][y][r]=min(f[i][y][r],f[i-1][l][r]+move[l][y]);
         }
        for(int l=1;l<=4;l++)
         for(int r=1;r<=4;r++)
         {
             if(f[i-1][l][r]>40000) continue;
             f[i][l][y]=min(f[i][l][y],f[i-1][l][r]+move[r][y]);
         }
    }
    for(int i=0;i<=4;i++)
     for(int j=0;j<=4;j++)
      ans=min(ans,f[n][i][j]);
    printf("%d",ans);
}

 

舞蹈家怀特先生