题意:一个跳舞机上有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; }