Git入门指南六:移除文件和移动文件
题目链接:uva 1291 - Dance Dance Revolution
题目大意:有一台跳舞机,中间位置是0,然后从0的右边开始顺时针分别是1,2,3,4;从0到1,2,3,4要消耗2点体力;每个位置到斜角的消耗的体力为3点(例如1到2,4);到对角消耗的体力4点(1到3);原地不动消耗的体力为1;现在题目给出一个序列是要求踩的位置,两只脚的初始位置都在0,在跳得过程中不能两只脚同时放在一个位置上,求消耗的最小体力值。
解题思路:dp[i][l][r]表示在第i个目标位置,左脚在l上,右脚在r上的最小体力值。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N = 1005; const int M = 10; const int INF = 0x3f3f3f3f; int n, dp[N][M][M], val[M][M], p[N]; bool init() { n = 1; while (scanf("%d", &p[n]) == 1 && p[n]) n++; n--; for (int i = 1; i < 5; i++) { val[i][0] = val[0][i] = 2; val[i][i] = 1; } val[1][2] = val[1][4] = val[2][1] = val[2][3] = 3; val[3][2] = val[3][4] = val[4][3] = val[4][1] = 3; val[1][3] = val[3][1] = val[2][4] = val[4][2] = 4; return n > 1; } int solve () { memset(dp, INF, sizeof(dp)); dp[0][0][0] = 0; for (int i = 1; i <= n; i++) { int u = p[i]; for (int l = 0; l < 5; l++) { for (int r = 0; r < 5; r++) { if (u != r) dp[i][u][r] = min(dp[i][u][r], dp[i-1][l][r] + val[l][u]); if (u != l) dp[i][l][u] = min(dp[i][l][u], dp[i-1][l][r] + val[r][u]); } } } int ans = INF; for (int i = 1; i < 5; i++) { for (int j = 1; j < 5; j++) ans = min(ans, dp[n][i][j]); } return ans; } int main () { while (init()) { printf("%d\n", solve()); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。