uva 1291 dp

uva 1291 dp

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