uva 1291 - Dance Dance Revolution ( dp )

題目大意

如上圖，這是一個跳舞機，初始狀態兩個腳都在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)}

代碼
 

/**========================================== * 
  This is a solution for ACM/ICPC problem * * 
  @source：uva-1291 Dance Dance Revolution * 
  @author: shuangde *  
 @blog: blog.csdn.net/shuangde800 *  
 @email: zengshuangde@gmail.com *===========================================*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = 10010;
int n;int dir[MAXN];
int f[MAXN][5][5];
inline int consume(int from, int to){    if(from==to) return 1; 
   if(from==0 || to==0) return 2;  
  int res = abs(from-to);  
  if(res == 1 || res==3) return 3;  
  if(res == 2) return 4;
}int main(){    while(~scanf("%d", &dir[0]) && dir[0]){        n = 1;   
     while(~scanf("%d", &dir[n]) && dir[n]) ++n;      
  memset(f, INF, sizeof(f));     
   for(int i=0;
 i<=4; ++i)            f[0][0][i] = f[0][i][0] = consume(0, i); 
       for(int i=0; i<n-1; 
++i){            int s = dir[i];    
        int next = dir[i+1];     
       for(int j=0;
 j<=4; 
++j) if(s!=j){                if(f[i][s][j] != INF){                
    f[i+1][s][j] = min(f[i+1][s][j], f[i][s][j] + 1);  
                  for(int k=0; 
k<=4; 
++k){                        f[i+1][next][j] = min(f[i+1][next][j], f[i][s][j] +consume(s, next));   
                      f[i+1][s][next] = min(f[i+1][s][next], f[i][s][j] +consume(j, next));  
                   }                 }                if(f[i][j][s] != INF){         
           f[i+1][j][s] = min(f[i+1][j][s], f[i][j][s] + 1);  
                   for(int k=0; k<=4; 
++k){                        f[i+1][next][s] = min(f[i+1][next][s], f[i][j][s] +consume(j, next));   
                      f[i+1][j][next] = min(f[i+1][j][next], f[i][j][s] +consume(s, next));       
              }                 }            }        }         int ans = INF;       
 int s = dir[n-1];   
     for(int i=0; 
i<=4; 
++i)if(i!=s){            ans = min(ans, min(f[n-1][i][s], f[n-1][s][i]));      
          }        printf("%d\n", ans);  
  }    return 0;}