首页 > 代码库 > NYOJ 740 “炫舞家“ST

NYOJ 740 “炫舞家“ST

2024-07-12 16:42:50   221人阅读

“炫舞家“ST

时间限制：3000 ms  |  内存限制：65535 KB
难度：3
 
描述
ST是一个酷爱炫舞的玩家。TA很喜欢玩QQ炫舞，因此TA也爱屋及乌的喜欢玩跳舞机（Dance Dance Revolution，DDR）。但是TA每天还要努力的学习，因此TA希望每次都保存最多的体力来学习。

DDR的主要内容是用脚来踩踏板。踏板有4个方向的箭头，用1，2，3，4来代表，如下图所示。

                                                    

 游戏规则如下：
   每首歌曲有一个箭头序列，游戏者必须按照这个序列依次用某一只脚踩相应的踏板。在任何时候，两只脚都不能在同一个踏板上，但可以同时待在中心位置0（一开始游戏的时候，游戏者的双脚都在中心位置0处）。
   每一个时刻，TA必须移动而且只能移动TA的一只脚去踩相应的箭头，而另一只脚不许移动。这样，TA跳DDR的方式可以用一串数字L1L2………Ln来表示。
   其中体力消耗规则如下：
1、 从中心往任何一个箭头耗费2个单位体力；
2、 从任何一个箭头移动到相邻箭头耗费3个单位体力（1和3相对，2和4相对）耗费4个单位体力。
3、 留在原地在踩一下只需要1单位。 
现在炫舞家ST很想学习但是又想玩DDR。因此，TA希望厉害的程序员你可以帮TA编写一个程序计算出TA因该怎样移动他的双脚（即，对于每个箭头，选一只脚去踩它），才能用最少的体力完成给定的舞曲。
例如，给出22140，总的体力耗费为2+1+2+3=8单位。 

 
输入
输入文件将包括一系列的方向序列。每个方向序列包含一个数字序列。每个输入序列应该是数字1、2、3或4,每个代表四个方向之一。一个值为0的方向序列表示方向的结束序列。和这个值应该被排除在方向序列（每个方向序列输入最多包含10000个数字）。输入文件结束为输入序列只有单独的一个0。
输出
对于每个方向序列,输出最少单位的体力消耗值。结果应该是一个整数在单独的一行。任何多余的白空格或空行将不被接受。
样例输入
2 3 3 3 3 1 2 03 2 2 1 2 00
样例输出
129
来源
BE玩家
上传者
ACM_钟诗俊

解题：我觉得这题目还是比较难得。。。弱菜无题能AC啊

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 int dp[10010][6][6],d[10010];12 int cost[5][5];13 void init() {14     cost[0][1]=cost[0][2]=cost[0][3]=cost[0][4]=2;15     cost[1][2]=cost[2][1]=cost[2][3]=cost[3][2]=cost[3][4]=cost[4][3]=cost[4][1]=cost[1][4]=3;16     cost[1][3]=cost[3][1]=cost[2][4]=cost[4][2]=4;17     cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=1;18 }19 int main() {20     int i,j,k,n,ans,x,y;21     init();22     while((~scanf("%d",&d[1]))&&d[1]) {23         for(i = 2; d[i-1]; i++) scanf("%d",d+i);24         n = i;25         for(i = 0; i < n; i++)26             for(j = 0; j < 5; j++) {27                 for(k = j; k < 5; k++)28                     dp[i][j][k] = dp[i][k][j] = 100000005;29             }30         dp[0][0][0] = 0;31         ans = 100000005;32         for(i = 1; i < n; i++) {33             for(j = 0; j < 5; j++) {34                 if(d[i] == j) continue;35                 x = y = 100000005;36                 for(k = 0; k < 5; k++) {37                     if(k != j || k+j == 0) {38                         if(x > dp[i-1][k][j]+cost[k][d[i]])39                             x = dp[i-1][k][j]+cost[k][d[i]];40                         if(y > dp[i-1][j][k]+cost[k][d[i]])41                             y = dp[i-1][j][k]+cost[k][d[i]];42                     }43                 }44                 dp[i][j][d[i]] = dp[i][d[i]][j] = min(x,y);45                 if(dp[n-1][j][d[i]] < ans) ans = dp[n-1][j][d[i]];46             }47         }48         printf("%d\n",ans);49     }50     return 0;51 }
View Code

 

 


联系
我们