游戏者必须按照这个序列一次用某一只脚踩相应的踏板。在任何时候,两只脚不能在同一个踏板上,但可以同时在中心位置0。每一个时刻,HH必须移动他的一只脚去踩相应的箭头,另一只脚不能动。每跳完一个曲子,HH会计算他的总体力消耗。规定:从中心移动到任意一个箭头耗费2单位体力;从任何一个箭头到相邻的箭头耗费3单位体力;从一个箭头到相对的箭头耗费4单位体力;留在原地再踩一下耗费1单位体力。
HH想花尽量少的体力,你能帮助他么?
f[i][j][k] 存一下所占的两个位置j,k (0,1,2,3,4)
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N=1e5+2,inf=0x3f3f3f3f; int n,f[N][5][5],c[5][5]; void init(){ int i; for(i=0;i<=4;i++) c[i][i]=1; for(i=1;i<=3;i++)c[i][i+1]=c[i+1][i]=3; c[4][1]=c[1][4]=3,c[3][1]=c[1][3]=c[2][4]=c[4][2]=4; for(i=1;i<=4;i++)c[0][i]=c[i][0]=2; } int solve(){ int x,i,j; for(int k=1;k<N;k++) for(i=0;i<5;i++) for(j=0;j<5;j++) f[k][i][j]=inf; n=0; f[0][0][0]=0; while(cin>>x,x){ n++; for(i=0;i<5;i++) for(j=0;j<5;j++) f[n][x][j]=min(f[n][x][j],f[n-1][i][j]+c[x][i]); for(i=0;i<5;i++) for(j=0;j<5;j++) f[n][i][x]=min(f[n][i][x],f[n-1][i][j]+c[x][j]); } if(n==0) return 0; int ans=inf; for(i=0;i<5;i++) for(j=0;j<5;j++) if(i!=j)ans=min(ans,f[n][i][j]); cout<<ans+2<<endl; return 1; } signed main(){ init(); while(solve()) ; }
标签:体力,include,int,箭头,HH,uva,1291,耗费 From: https://www.cnblogs.com/towboa/p/16837941.html