Please ensure that adb is correctly located at 最新详细方案

题目链接: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;
}


Please ensure that adb is correctly located at 最新详细方案

上一篇:关于zedboard无法烧写bit流文件的解决办法


下一篇:excel中拼sql格式,批量导入数据