uva1291

这题说的给了 一 个 图，每次 按照他给的顺序 跳格子 给了 每种 格子之间的 转换 代价 求最后 转换代价

dp[i][j] 表示 左脚在i 右脚 在j 的最小代价 然后用滚动数组 ，就可以不断说的转化，然后固定一个 另一个变换

dp[n][i]  dp[i][n]

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll maxv=1e18;
ll dp[2][5][5];
void inti(int now){
     for(int i=0; i<5; ++i)
        for(int j=0; j<5; ++j)
       dp[now][i][j]=maxv;
}
ll cal(int a, int b)
{
     if( a==0 || b==0 ) return 2;
     if( a == b ) return 1;
     int t1 = a+1 ;
     if( t1 > 4 )  t1=1;
     if( t1 == b ) return 3;
     t1 = a-1;
     if( t1 < 1 )  t1=4;
     if( t1 == b ) return 3;
     return 4;
}
int main()
{
     int n;
     while(scanf("%d",&n)==1&&n){
          int now=0;
          int late=1;
          inti(0);
          dp[0][0][n]=2;
          dp[0][n][0]=2;
          int per=n;
          while(true){
              scanf("%d",&n);
              if(n==0) break;
              per=n;
              now=1-now;
              late=1-late;
              inti(now);
              for(int i=0; i<5; ++i)
                for(int j=0; j<5; ++j){
                       if(i==j||i==n)continue;
                      dp[now][n][i] = min(dp[late][j][i]+cal(j,n),dp[now][n][i]);
                }
              for(int i=0; i<5; ++i)
              for(int j=0; j<5; ++j){
                  if(i==j||i==n) continue;
                  dp[now][i][n]=min( dp[now][i][n] , dp[late][i][j]+cal(j,n) );
              }
          }
          ll ans=maxv;
          for(int i=0;i<5 ; ++i)
            ans=min(ans, min( dp[now][per][i],dp[now][i][per]));
          printf("%lld
",ans);
     }

    return 0;
}