首页 > 其他分享 >uva 1291

uva 1291

时间:2022-10-29 01:22:21浏览次数:60  
标签:体力 include int 箭头 HH uva 1291 耗费

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

相关文章

  • uva 11795
      题目意思还是有点绕的,想了好一会大体上是一个状压dp(废话 f[j],当当前拥有武器集合为j时,消灭所有怪物的方案数像线性dp一样,但可以去掉一维 f[j]+=f[t],t=j^(1......
  • uva 1456
    比如,手机可能位于 5 个区域中,概率分别为 0.3,0.05,0.1,0.3,0.25,则一种方法是先同时访问 \{c1,c2,c3\},再同时访问 {c_4,c_5},访问区域数量的期望为  3*(0.3+0.05......
  • uva11404
    删去字符串S中的一些字符,使剩下的字符组成最长的回文串(顺序连接) 区间dpf[i][j] f[i][j]=f[i+1][j-1]  i==j =min(f[i+1][j],f[i][j-1]) #include......
  • uva 11552
    给你一个长度 k ,一个字符串 S(都为小写字母),保证 S 的长度为 k的整数倍。将 S 按顺序分为 S/k 组,组内字符可以重新排列问最少有几个块?(如fff,ww) 枚举开头......
  • uva 10534
    给一个序列A,求一个最长子序列,长度为2k+1满足前k+1个数递增,后k个递减  LIS板子题,正反各求一次,枚举中间的交点 #include<iostream>#include<cstring>#include<al......
  • uva 1424
    给定一个长度为 n1​ ( n1​≤100 )的点的无向连通图和一个长度为 n 的序列 A ( n≤200 ),1<=A[i]<=n1希望修改尽量少的数,使得序列的任意相邻两个数在图上是是......
  • uva 11584
    给一个字符串,划分成最少的回文串如aaadbccb---->aadbccb f[i]=miin{f[j]+1}j<i, 且s[j...i]是回文串 #include<iostream>#include<cstring>using......
  • uva 1169
    地图上有n个点(x,y),机器人从(0,0)出发到每个点捡垃圾(w[i]),承载最大重量为m在每个点都可以返回(0,0)点放置垃圾最短路程?n<1e5,m<100 看完范围只能设f[i],考虑前i......
  • uva 10891
    A,B两人从序列两端轮流取数,每次可以取多个(甚至取完)分数为所取数字的和,假设两人足够聪明,求得分差 f[i][j]区间[i,j],先手取得最大得分转移到取完后对方的序列 f[i]......
  • uva 1428
    题目求三元组(i,j,k),i<j<k,满足a[i]<a[j]<a[k],有多少组?(a[i]<=1e5)枚举j,考虑a[i]<a[j]有多少i满足这个条件注意到a[i]的范围,我们用一个桶v[i]存以下......