游戏者必须按照这个序列一次用某一只脚踩相应的踏板。在任何时候，两只脚不能在同一个踏板上，但可以同时在中心位置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()) ;
 }

 

原文地址：http://www.cnblogs.com/towboa/p/16837941.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性