程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> uva 1291 dp

uva 1291 dp

編輯:關於C++
UVA 1291 - Dance Dance Revolution

有一個跳舞機。原點為0,有四個方向,上左下右,分別標成(1234),初始玩家兩只腳站在 0 位置,跳舞機會給出一串數字,玩家要按照順序踩下四個方向的數字。移動腳會消耗玩家的能量,從0位置移動到四個方向消耗2點能量,從一個方向移動到另一個相鄰的方向消耗3點能量,從一個方向移動到相反方向消耗4點能量,原點踩一下消耗1點能量。問你踩出這串數子最少要花多少能量。

 

根據能量消耗關系,我們可以發現當前兩只腳踩的方向才是重點。然而要記錄兩只腳的方向麼?其實不用,因為我們可以發現兩只腳的狀態是互不影響的,而且單跳到第i個數字的時候,有一只腳的位置是確定的。


dp[i][j]表示跳到第i個數字的時候那只不確定的腳的位置是j的時候所消耗能量的最小值。那麼跳第i+1個數字的時候可以由兩只腳(a[i], j)跳過去,將會有兩種結果(a[i+1], j) 和(a[i+1], a[i])。得到兩個狀態dp[i+1][j], dp[i+1][a[i]]。

dp[i+1][j] = dp[i+1][j] + _get(a[i], a[i+1]);
dp[i+1][a[i]] = dp[i+1][j] + _get(j, a[i+1]);

_get(a, b) 求出a跳到b所消耗的能量。其實就是幾個特判。

然後在dp[n][*]裡面找個最小值。

 

 

#include 
using namespace std;
const int INF = 999999999;


int k;
int a[100010];
int _read() {
	int tmp;
	for ( k=1; scanf(%d, &tmp) && tmp; ) {// 	cout << tmp << endl;
		a[k++] = tmp;
	}
	// a[k++] = tmp;
	return k;
}

int dp[100010][5];

int _get(int a, int b) {
	if (a == 0) return 2;
	if (a == b) return 1;
	if (abs(a-b) == 1 || abs(a-b) == 3) return 3;
	if (abs(a-b) == 2) return 4;
}

int main () {// cout << * << endl;
	for (; _read() != 1; ) {// cout << k << endl;

		for (int i=0; i<=k; i++) {
			fill(dp[i], dp[i]+5, INF);
		}

		dp[1][0] = _get(0, a[1]);

		for (int i=2; i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved