意甲冠军:跳舞机有一个上5积分,分别central, top, bottom, left, right分,区区足站立还是需要1点物理,从一个单纯的脚central点上须要2点体力,从一个点上移动到相邻的点上须要3点体力,从一个点移动到对面的点上须要4点体力,初始的时候双脚都在central点上,给出一系列的舞步,求最少须要多少的体力来完毕.

思路:设dp[k][i][j]为在第k个舞步的时候,左右脚分别在i,j点上的最少体力.

转移的时候仅仅需考虑从上一个舞步的左脚还是右脚到当前舞步,详细就看程序里吧, 用了滚动数组.

#include <cstdio>

#include <algorithm>

#include <memory.h>

using namespace std;

const int MAX = 5;

int dp[2][MAX][MAX];

inline bool is_opposite(int i, int j){

	return i == 1 && j == 3 || i == 2 && j == 4;

}

inline int consumption(int i, int j){

	if(i == j)return 1;

	else if(i == 0)return 2;

	else if(is_opposite(i, j) || is_opposite(j, i))return 4;

	else return 3;

}

int main(int argc, char const *argv[]){

	int side;

	while(scanf("%d", &side) && side){

		int f = 1, ans = 0x20202020;

		memset(dp, 0x20, sizeof(dp));

		dp[0][0][0] = 0;

		do{

			//move the left foot

			for(int i = 0; i <= 4; ++i){

				for(int j = 0; j <= 4; ++j){

					if(side != j){

						dp[f][side][j] = min(dp[f][side][j], dp[f ^ 1][i][j] + consumption(i, side));

					}

				}

			}

			//move the right foot

			for(int i = 0; i <= 4; ++i){

				for(int j = 0; j <= 4; ++j){

					if(side != i){

						dp[f][i][side] = min(dp[f][i][side], dp[f ^ 1][i][j] + consumption(j, side));

					}

				}

			}

			scanf("%d", &side);

			f ^= 1;

			memset(dp[f], 0x20, sizeof(dp[f]));

		}while(side);

		printf("%d\n", *min_element(&dp[f ^ 1][0][0], &dp[f ^ 1][4][4]));

	}

	return 0;

}