题目大意：有4个位置，每次从一个位置移动到另一个位置需要特定花费，求一串指定序列的最短花费。每次只能一只脚移动，或移动并踩下。
用d[i][j][u]表示前i个位置完成且在(j,u)的状态最小花费是多少，(j,u)其中之一必须和a[i]相等，，假设是j和a[i]相等，那么可能上一个状态也是(j,u)，或者上一个状态是(k,u)，注意上一个状态不能是(j,k)，因为这样需要左脚踩踏，右脚移动，不合法。至于移动的到底是左脚还是右脚，不用关心，因为总是可以进行转移。
状态转移方程：
d[i][j][u]=min { d[i-1][j][u]+1,min {d[i-1][k][u]+cost[j][k] } }（j==a[i]）
d[i][j][u]=min { d[i-1][j][u]+1,min {d[i-1][j][k]+cost[k][u] } }（u==a[i]）
#include<stdio.h>#include<stdlib.h>int d[2][7][7];int cost[5][5]={{1,2,2,2,2},{2,1,3,4,3},{2,3,1,3,4},{2,4,3,1,3},{2,3,4,3,1}};int main(void){int i,j,u,cur,min,minp;scanf("%d",&u);while(u!=0){for(i=0;i<5;i++){for(j=0;j<5;j++){d[0][i][j]=(1<<29);}}cur=0;d[0][0][u]=d[0][u][0]=2;scanf("%d",&u);while(u!=0){cur^=1;for(i=0;i<5;i++){for(j=0;j<5;j++){d[cur][i][j]=(1<<29);}}for(i=0;i<5;i++){if(i!=u){minp=d[cur^1][i][u]+1;for(j=0;j<5;j++){if(j!=i){minp=((d[cur^1][i][j]+cost[j][u]<minp)?(d[cur^1][i][j]+cost[j][u]):minp);}}d[cur][i][u]=d[cur][u][i]=minp;}}d[cur][u][u]=(1<<29);scanf("%d",&u);}min=(1<<29);for(i=0;i<5;i++){for(j=0;j<5;j++){if(d[cur][i][j]<min){min=d[cur][i][j];}}}printf("%d\n",min);scanf("%d",&u);}return 0;}
穿别人的鞋，走自己的路，让别追去吧
