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

本文出自：http://blog.csdn.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;}