UVa 1291 Dance Dance Revolution

dp[k][i][j]表示第k步左脚在位置 i，右脚在位置 j 状态时的最小能量消耗.

dp[k][i][j] = min( dp[ k - 1 ][x][j] + cost[x][ step[k] ], dp[ k - 1 ][i][x] + cost[x][ step[k] ] );

这题很坑爹的没有数据范围，数组我随便开的，居然1Y了……

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 10010;
 9 const int INF = 1 << 30;
10 
11 int step[MAXN];
12 int dp[MAXN][6][6];
13 int cost[6][6];
14 int N;
15 
16 void init()
17 {
18     for ( int i = 0; i < 5; ++i ) cost[i][i] = 1;
19     for ( int i = 1; i < 5; ++i ) cost[0][i] = 2;
20     for ( int i = 1; i < 5; ++i )
21     {
22         cost[i][i + 1] = 3;
23         cost[i + 1][i] = 3;
24     }
25     cost[1][4] = 3;
26     cost[4][1] = 3;
27     cost[1][3] = 4;
28     cost[3][1] = 4;
29     cost[2][4] = 4;
30     cost[4][2] = 4;
31 
32     return;
33 }
34 
35 void DP()
36 {
37     dp[0][0][0] = 0;
38     for ( int k = 1; k < N; ++k )
39     {
40         for ( int i = 0; i <= 4; ++i )
41         {
42             int j = step[k];
43             for ( int x = 0; x <= 4; ++x )
44             {
45                 dp[k][j][i] = min( dp[k][j][i], dp[k - 1][x][i] + cost[x][j] );
46                 dp[k][i][j] = min( dp[k][i][j], dp[k - 1][i][x] + cost[x][j] );
47             }
48         }
49     }
50 
51     int ans = INF;
52     for ( int i = 0; i <= 4; ++i )
53     for ( int j = 0; j <= 4; ++j )
54         ans = min( ans, dp[N - 1][i][j] );
55 
56     printf( "%d\n", ans );
57 
58     return;
59 }
60 
61 int main()
62 {
63     init();
64     int a;
65     while( scanf( "%d", &a ), a )
66     {
67         step[1] = a;
68         N = 1;
69         while ( scanf( "%d", &step[ ++N ] ), step[N] );
70 
71         for ( int i = 0; i <= N; ++i )
72             for ( int j = 0; j <= 4; ++j )
73                 for ( int k = 0; k <= 4; ++k )
74                     dp[i][j][k] = INF;
75 
76         DP();
77     }
78     return 0;
79 }