uva 1291 - Dance Dance Revolution ( dp )

本文出自 http://blog.csdn.net/shuangde800

题目：点击打开链接

题目大意

如上图，这是一个跳舞机，初始状态两个脚都在0, 状态表示为(0, 0), 然后跳舞机会给你一系列舞步方向，例如2,3,4,2,3.......

每次你必须选择一只脚移动到对应数字方向的各格子上。

例如从初始状态(0,0),要移到1, 可以选择左脚或者右脚移上去，对应的状态为（1, 0）, （0,1）

有一个限制，除了初始状态可以是（0, 0），之后的两只脚就不能再同时在一个格子上！

移动脚要耗费体力， 从0移动到其它各自都是耗费2, 从1,2,3,4之间，如果是移动到相邻的格子，比如1->2, 1->4, 3->2, 4->3，耗费体力3

如果是移动到对面的格子，比如1->3, 2->4，耗费体力4。

如果某一步，停止不动，耗费体力1

给一串方向，问最少用多少体力可以完成这些动作？

思路

f(i, j, k), 表示第i步，状态为（j，k）时花费的最少体力
那么不难推出转移方程式：

假设当前这个舞步是在ｓ，那么符合这一步的所有状态有：
f(i, 0..4, s), f(i, s, 0...4)

然后可以根据上面的状态推出下一舞步的最少体力话费

假设下一舞步是next

那么

如果f(i, j, s), (0<=j<=4)状态可达
则可推出下一个的状态
f(i+1, j, s) = f(i, j, k) + 1; // 停在当前不动
f(i+1, next, s) = min{ f(i, j, s) + consume(j, next)}
f(i+1, j, next) = min{ f(i, j, s) + consume(s, next)}

同理，如果f(i, s, j), (0<=j<=4)状态可达
也可推出下一个状态:
f(i+1, s, j) = f(i, j, k) + 1; // 停在原地不动
f(i+1, next, j) = min{ f(i, s, j) + consume(s, next)}
f(i+1, s, next) = min{ f(i, s, j) + consume(j, next)}

代码

<script src="https://code.csdn.net/snippets/553.js" type="text/javascript"></script>