题目描述
上上下下的电梯要到点$n$
样例
6 3
-1 0 2
19
算法1
(A*)
显然BFS即可。如果数据大的话可以考虑用A*,估价函数即为当前楼层到$n$的距离乘以$2$(显然是理想最优,因为还要掰开关)。
此题有一点没有说清,就是可以掰开关但电梯不动,不掰开关而电梯直接上升。
C++ 代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
inline int jd(const int a){
return ((a>0)?a:(-a));
}
inline int init(const int a,const int b,const int c){
return (b<=a&&a<=c);
}
int n,m;
int c[25];
int dis[25][1010];
struct point{
int u,k,v,f;
};
bool operator < (const point a,const point b){
return a.v+a.f>b.v+b.f;
}
priority_queue<point>sq;
int main(){
int np;
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
if(!c[i]) np=i;
}
for(int i=0;i<=m;i++)
for(int j=0;j<=n;j++)
dis[i][j]=2000000000;
dis[1][np]=0;
sq.push((point){1,np,0,(n-1)*2});
point tmp;
int flg=1;
while(!sq.empty()){
tmp=sq.top();sq.pop();
if(dis[tmp.k][tmp.u]<tmp.v) continue;
//printf("**%d %d %d\n",tmp.u,tmp.k,tmp.v);
if(tmp.u==n){
printf("%d",tmp.v);
flg=0;
break;
}
if(init(tmp.u+c[tmp.k],1,n)&&dis[tmp.k][tmp.u+c[tmp.k]]>tmp.v+2*jd(c[tmp.k])){//不动上升
dis[tmp.k][tmp.u+c[tmp.k]]=tmp.v+2*jd(c[tmp.k]);
sq.push((point){tmp.u+c[tmp.k],tmp.k,tmp.v+2*jd(c[tmp.k]),(n-tmp.u-c[tmp.k])*2});
}
if(tmp.k>1&&dis[tmp.k-1][tmp.u]>tmp.v+1){//掰
dis[tmp.k-1][tmp.u]=tmp.v+1;
sq.push((point){tmp.u,tmp.k-1,tmp.v+1,tmp.f});
}
if(tmp.k<m&&dis[tmp.k+1][tmp.u]>tmp.v+1){//掰x2
dis[tmp.k+1][tmp.u]=tmp.v+1;
sq.push((point){tmp.u,tmp.k+1,tmp.v+1,tmp.f});
}
}
if(flg) printf("-1");
return 0;
}
判定是否在1~n楼层内
大佬问下,那个init的作用是什么啊?
$\huge\color{red}{\text{系统检测到此人为巨佬}}$