UVA 1291 Dance Dance Revolution(DP)

題意:一個跳舞機上有5個點,分別為central, top, bottom, left, right點,一只腳原地踏步需要1點體力,一只腳從central點上移到其他點上需要2點體力,從一個點上移動到相鄰的點上需要3點體力,從一個點移動到對面的點上需要4點體力,初始的時候雙腳都在central點上,給出一系列的舞步,求最少需要多少的體力來完成.

思路:設dp[k][i][j]為在第k個舞步的時候,左右腳分別在i,j點上的最少體力.

轉移的時候只需考慮從上一個舞步的左腳還是右腳到當前舞步,具體就看程序裡吧, 用了滾動數組.

#include 
#include 
#include 
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;
}