UVA1291----Dance Dance Revolution----3维DP

题目意思：

跳舞机

中间为0

上左下右分别为1，2，3，4

然后从0到其他消费2

相邻的移动消费3

原地踏步消费1

相对移动消费2

给你一串舞步，初始双脚站在中间，问你跳完的最小消耗

思路：

简单的区间DP，但是自己写了好久啊，囧

令f[n][i][j]表示第n步时的左右脚分别为i,j的最小步数

则装态转移方程：

如果f(i, j, s), (0<=j<=4)状态可达

则可推出下一个的状态

f(i+1, j, s) = f(i, j, s) + 1; // 停在当前不动

f(i+1, next, s) = min{ f(i, j, s) + check(j, next)}

f(i+1, j, next) = min{ f(i, j, s) + check(s, next)}

同理，如果f(i, s, j), (0<=j<=4)状态可达

也可推出下一个状态:

f(i+1, s, j) = f(i, j, s) + 1; // 停在原地不动

f(i+1, next, j) = min{ f(i, s, j) + check(s, next)}

f(i+1, s, next) = min{ f(i, s, j) + check(j, next)}

推了很久啊

下面上代码：

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
  
int dp[20000][5][5];  
const int inf = 0x3f3f3f3f;  
  
int check(int st,int ed)  
{  
    if(st==ed)  
        return 1;  
    if(st==0 || ed==0)  
        return 2;  
    if(st==1)  
    {  
        if(ed == 2 || ed==4)  
            return 3;  
        return 4;  
    }  
  
    if(st==2)  
    {  
        if(ed == 1 || ed==3)  
            return 3;  
        return 4;  
    }  
  
    if(st == 3)  
    {  
        if(ed==2 || ed==4)  
            return 3;  
        return 4;  
    }  
  
    if(st==4)  
    {  
        if(ed == 1|| ed==3)  
            return 3;  
        return 4;  
    }  
}  
  
int main()  
{  
    int tmp;  
    while(1)  
    {  
        int cnt = 0;  
        memset(dp,inf,sizeof(dp));  
        dp[0][0][0] = 0;  
        int tmp2=0;  
        while(1)  
        {  
            scanf("%d",&tmp);  
            if(tmp == 0)  
                break;  
            cnt++;  
            for(int i=0;i<=4;i++)  
            {  
                dp[cnt][i][tmp2] = min(dp[cnt][i][tmp2],dp[cnt-1][i][tmp2]+1);  
                dp[cnt][tmp2][i] = min(dp[cnt][tmp2][i],dp[cnt-1][tmp2][i]+1);  
                dp[cnt][tmp][i] = min(dp[cnt][tmp][i],dp[cnt-1][tmp2][i]+check(tmp2,tmp));  
                dp[cnt][tmp2][tmp] = min(dp[cnt][tmp2][tmp],dp[cnt-1][tmp2][i]+check(i,tmp));  
                dp[cnt][tmp][tmp2] = min(dp[cnt][tmp][tmp2],dp[cnt-1][i][tmp2]+check(i,tmp));  
                dp[cnt][i][tmp] = min(dp[cnt][i][tmp],dp[cnt-1][i][tmp2]+check(tmp2,tmp));  
            }  
            tmp2 = tmp;  
        }  
        if(cnt==0)  
            break;  
        int ans = inf;  
        for(int i=0;i<=4;i++) if(i!=tmp2)  
                ans = min(dp[cnt][tmp2][i],ans);  
        for(int i=0;i<=4;i++) if(i!=tmp2)  
                ans = min(dp[cnt][i][tmp2],ans);  
        cout<<ans<<endl;  
    }  
    return 0;  
}

补充：web前端 , HTML/CSS  ,