题意：一个跳舞机，分上下左右中，中编号是0，然后从上开始逆时钟编号1、2、3、4，有一串你要踩的序列，从0到周围4个，花费为2，周围两个相邻的动一下是3，跳到对面去是4，同一格踩一下是1，两个脚不能同时踩在同一格，问你这串序列踩完最少的花费。
思路：LRJ黑书上的一道题，三维表示状态，dp[2][i][j],i.j分别表示左右脚放的位置，看见别人滚动数组节省空间，就学着写了，记得黑书上好像也是这样子的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int cost[5][5],d[2][5][5];
void init(){
for (int i = 1; i <= 4; i++){
cost[0][i] = cost[i][0] = 2;
cost[i][i] = 1;
}
cost[0][0] = 1;
for (int i = 1; i <= 3; i++)
cost[i][i+1] = cost[i+1][i] = 3;
cost[1][4] = cost[4][1] = 3;
cost[1][3] = cost[3][1] = 4;
cost[2][4] = cost[4][2] = 4;
}
int main(){
init();
int a;
while (scanf("%d",&a) != EOF && a){
memset(d[0],INF,sizeof(d[0]));
d[0][a][0] = d[0][0][a] = 2;
int pre = 0,cur;
while (scanf("%d",&a) != EOF && a){
cur = pre^1;
memset(d[cur],INF,sizeof(d[cur]));
for (int j = 0; j <= 4; j++)
for (int k = 0; k <= 4; k++)
d[cur][a][j] = min(d[cur][a][j],d[pre][k][j]+cost[a][k]);
for (int j = 0; j <= 4; j++)
for (int k = 0; k <= 4; k++)
d[cur][j][a] = min(d[cur][j][a],d[pre][j][k]+cost[a][k]);
pre = cur;
}
int ans = INF;
for (int i = 0; i <= 4; i++)
for (int j = 0; j <= 4; j++){
if (i == j)
continue;
ans = min(ans,d[cur][i][j]);
}
printf("%d\n",ans);
}
return 0;
}