算法：uva 1291 - Dance Dance Revolution （ dp ）

算法：uva 1291 - Dance Dance Revolution （ dp ）2014-01-03 csdn 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）}