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

本文出自：http://blog.****.net/dr5459

题目地址：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4037

题目意思：

跳舞机

中间为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;
}