学步园

d[ i ][ j ][ k ] 代表当前i个箭头已经跳过，左腿在j右腿在k时候的最小移动代价；

注意两条腿可以同时移动；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include <iostream>
using namespace std;
const int maxn = 110;
const int inf  = 1000000;
int c[5][5];
void init(){
  for(int i=1;i<=4;i++)
    c[i][0]=c[0][i]=2;
  for(int i=1;i<=4;i++){
     int te = i==4? 1:i+1;
     c[te][i]=c[i][te]=3;
     c[i][i] = 1;
  }
  c[0][0] = 1;
  c[1][3]=c[3][1]=4;
  c[2][4]=c[4][2]=4;
}
int d[10005][5][5],n,a[10010];
bool vis[10005][5][5];
/*top is 1, the left is 2, the bottom is 3, and the right is 4*/
int dp(int i,int j,int k){
  if(vis[i][j][k]) return d[i][j][k];
  vis[i][j][k] = true;
  int& ans = d[i][j][k];
  if(i==n){
      return d[i][j][k] = 0;
   }
  ans=inf;
  if(j==a[i+1]||k==a[i+1]){
     if(j==a[i+1]){
        for(int x=0;x<=4;x++){
             int add1 = k==x ? 0 : c[k][x];
             ans=min(ans,dp(i+1,j,x)+1+add1);
        }
     }
     else {
        for(int x=0;x<=4;x++){
             int add2 = j==x ? 0 : c[j][x];
             ans=min(ans,dp(i+1,x,k)+1+add2);
        }
     }
  }
  else {
     for(int x=0;x<=4;x++){
       int add1 = k==x ? 0 : c[k][x];
       int add2 = j==x ? 0 : c[j][x];
       ans=min(ans,dp(i+1,a[i+1],x)+c[j][a[i+1]]+add1);
       ans=min(ans,dp(i+1,x,a[i+1])+c[k][a[i+1]]+add2);
     }
  }
  return ans;
}
int main()
{
    init();
    int x;
    while(scanf("%d",&x)==1 && x){
       n=0;
       a[++n]=x;
       while(scanf("%d",&x)&&x){
          a[++n] = x;
       }
       memset(vis,false,sizeof(vis));
       printf("%d\n",dp(0,0,0));
    }
    return 0;
}