Time limit: 3.000 seconds
Mr. White, a fat man, now is crazy about a game
named ``Dance, Dance, Revolution". But his dance skill is
so poor that he
could not dance a dance, even if he dances arduously every time. Does ``DDR"
just mean him
a perfect method to squander his pounds? No way. He still
expects that he will be regarded as ``Terpsichorean
White" one day. So he is
considering writing a program to plan the movement sequence of his feet, so that
he
may save his strength on dancing. Now he looks forward to dancing easily
instead of sweatily.
``DDR" is a dancing game that requires the dancer to use
his feet to tread on the points according to the
direction sequence in the
game. There are one central point and four side points in the game. Those side
points
are classified as top, left, bottom and right. For the sake of
explanation, we mark them integers. That is, the
central point is 0, the top
is 1, the left is 2, the bottom is 3, and the right is 4, as the figure below
shows:
At the beginning the dancer‘s two feet stay on the
central point. According to the direction sequence, the
dancer has to move
one of his feet to the special points. For example, if the sequence requires him
to move to
the top point at first, he may move either of his feet from point
0 to point 1 (Note: Not both of his feet). Also,
if the sequence then
requires him to move to the bottom point, he may move either of his feet to
point 3,
regardless whether to use the foot that stays on point 0 or the one
that stays on point 1.
There is a strange rule in the game: moving both of
his feet to the same point is not allowed. For instance, if
the sequence
requires the dancer to the bottom point and one of his feet already sta ys on
point 3, he should
stay the very foot on the same point and tread again,
instead of moving the other one to point 3.
After dancing for a long time,
Mr. White can calculate how much strength will be consumed when he moves
from
one point to another. Moving one of his feet from the central point to any side
points will consume 2
units of his strength. Moving from one side point to
another adjacent side point will consume 3 units, such as
from the top point
to the left point. Moving from one side point to the opposite side point will
consume 4
units, such as from the top point to the bottom point. Yet, if he
stays on the same point and tread again, he will
use 1 unit.
Assume that
the sequence requires Mr. White to move to point 1 2 2 4. His feet may stays
on
(point 0, point 0) (0, 1) (2, 1) (2, 1) (2, 4). In this couple of
integers, the former number
represents the point of his left foot, and the
latter represents the point of his right foot. In this way, he has to
consume
8 units of his strength. If he tries another pas, he will have to consume much
more strength. The 8
units of strength is the least cost.
Input
The input file will consist of a series of direction
sequences. Each direction sequence contains a sequence of
numbers. Ea ch
number should either be 1, 2, 3, or 4, and each represents one of the four
directions. A value
of 0 in the direction sequence indicates the end of
direction sequence. And this value should be excluded from
the direction
sequence. The input file ends if the sequence contains a single
0.
Output
For each
direction sequence, print the least units of strength will be consumed. The
result should be a single
integer on a line by itself. Any more white spaces
or blank lines are not allowable.
Sample Input
1 2 2 4 0
1 2 3 4
1 2 3 3 4 2 0
0
Sample
Output
8
22
Shanghai 2000-2001
题解：
线性动态规划。维护一个三维数组f[i][x][y]表示在第i步左脚在x，右脚在y消耗最小的体力。
注意初始化f=MAX_NUMBER。f[1][a[1]][0]=2;f[1][0][a[1]]=2;
动态转移方程：
f[i][a[i]][j]=min(f[i][a[i]][j],f[i-1][k][j]+effort(k,a[i]));
f[i][j][a[i]]=min(f[i][j][a[i]],f[i-1][j][k]+effort(k,a[i]));
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdbool.h> 4 int i,j,n, 5 a[11000],f[11000][5][5]; 6 7 int 8 pre() 9 { 10 memset(a,0,sizeof(a)); 11 memset(f,3,sizeof(f)); 12 return 0; 13 } 14 15 int 16 init() 17 { 18 while(true) 19 { 20 n++; 21 scanf("%d",&a[n]); 22 if(a[n]==0) 23 { 24 n--; 25 break; 26 } 27 } 28 29 f[1][a[1]][0]=2; 30 f[1][0][a[1]]=2; 31 return 0; 32 } 33 34 int 35 max(int a,int b) 36 { 37 if(a>b) return(a); 38 else return(b); 39 } 40 41 int 42 min(int a,int b) 43 { 44 if(a<b) return(a); 45 else return(b); 46 } 47 int 48 effort(int a,int b) 49 { 50 int p; 51 if((min(a,b)==0)&&(max(a,b)!=0)) return(2); 52 p=max(a,b)-min(a,b); 53 if(p==1 || p==3) return(3); 54 if(p==2) return(4); 55 if(p==0) return(1); 56 } 57 58 int 59 dp() 60 { 61 int i,j,k,mini; 62 for(i=2;i<=n;i++) 63 for(j=0;j<=4;j++) 64 for(k=0;k<=4;k++) 65 { 66 f[i][a[i]][j]=min(f[i][a[i]][j],f[i-1][k][j]+effort(k,a[i])); 67 f[i][j][a[i]]=min(f[i][j][a[i]],f[i-1][j][k]+effort(k,a[i])); 68 } 69 70 mini=35111111; 71 for(i=0;i<=4;i++) 72 mini=min(mini,min(f[n][a[n]][i],f[n][i][a[n]])); 73 74 printf("%d\n",mini); 75 return 0; 76 } 77 78 int 79 main() 80 { 81 while(true) 82 { 83 pre(); 84 n=1; 85 scanf("%d",&a[n]); 86 if(a[n]==0) break; 87 init(); 88 dp(); 89 } 90 return 0; 91 }
[LA] 2031 Dance Dance Revolution,布布扣,bubuko.com
[LA] 2031 Dance Dance Revolution
原文：http://www.cnblogs.com/sxiszero/p/3623513.html