题目传送门
题意：给一串跳舞的动作，至少一只脚落到指定的位置，不同的走法有不同的体力消耗，问最小体力消费多少
分析：dp[i][j][k] 表示前i个动作，当前状态(j, k)的最小消费，状态转移方程：(a[i], k) <- min (a[i-1], k) + cost以及(a[i-1], a[i]) <- min (a[i-1], k) + cost, (k, a[i])和(a[i], a[i-1])情况类似，最后再去最小值就行了
收获：四个状态转移方向
代码：
/************************************************* Author :Running_Time* Created Time :2015-8-15 14:31:31* File Name :UVA_1291.cpp************************************************/#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int a[MAXN];
int dp[MAXN][5][5];int cal(int x, int y) {int ret;if (x == y) ret = 1;else {if (y == 0) ret = 2;else {if (abs (x - y) == 2) {ret = 4;}else ret = 3;}}return ret;
}int main(void) { //UVA 1291 Dance Dance Revolutionint n = 0;while (scanf ("%d", &a[++n]) == 1) {if (a[1] == 0) break;while (a[n] != 0) {scanf ("%d", &a[++n]);}n--;memset (dp, INF, sizeof (dp));dp[1][a[1]][0] = (a[1] == 0 ? 1 : 2);dp[1][0][a[1]] = (a[1] == 0 ? 1 : 2);for (int i=2; i<=n; ++i) {for (int j=0; j<=4; ++j) {int c1 = cal (a[i], j);int c2 = cal (a[i], a[i-1]);int x = a[i], y = a[i-1];dp[i][x][y] = min (dp[i][x][y], dp[i-1][j][y] + c1);dp[i][j][x] = min (dp[i][j][x], dp[i-1][j][y] + c2);dp[i][y][x] = min (dp[i][y][x], dp[i-1][y][j] + c1);dp[i][x][j] = min (dp[i][x][j], dp[i-1][y][j] + c2);}}int ans = INF;for (int i=0; i<=4; ++i) {ans = min (ans, min (dp[n][i][a[n]], dp[n][a[n]][i]));}printf ("%d\n", ans); n = 0;}return 0;
}