根据题目描述，只有一开始会站在0这个格子上，以后不会向这个格子移动
假设f[i][j][k] 为 当前时间i，两只脚分别在j，k两个格子上的最小体力花费
第i个时间的状态为f[i][a[i]][k]或者f[i][j][a[i]]，即有一只脚在指定格子上，所以分两种情况枚举
转移方程
f[i][j][a[i]] = min(f[i][j][a[i]],f[i-1][j][k]+move(a[i],k));
f[i][a[i]][k] = min(f[i][a[i]][k],f[i-1][j][k]+move(a[i],j));（j,k∈(0,4)）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define N 10010 int a[N]; int f[N][5][5]; int n,ans = 100000; int odd(int x) { if (x%2) return 1;else return 0;} int move(int x,int y) { if (x == y) return 1; if (!(x && y)) return 2; if (odd(x) == odd(y)) return 4; return 3; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(f,127/4,sizeof(f)); f[0][0][0] = 0; for (int i=1;i<=n;i++) for (int j=0;j<=4;j++)//注意从0开始枚举，因为一开始在0格子上 for (int k=0;k<=4;k++) { f[i][j][a[i]] = min(f[i][j][a[i]],f[i-1][j][k]+move(a[i],k)); f[i][a[i]][k] = min(f[i][a[i]][k],f[i-1][j][k]+move(a[i],j)); } for (int i=0;i<=4;i++)//注意从0开始枚举 for (int j=0;j<=4;j++) ans = min(ans,f[n][i][j]); printf("%d",ans); }
原文：http://www.cnblogs.com/liumengyue/p/5617959.html
