做网站就业要会什么问题/站长工具seo综合查询是什么

传送门

题意：有一个楼，有l层楼，每层楼h长w宽， 然后每层楼都有人，有墙，有楼梯，每个人都有营救的价值，现在给出这个楼的信息，问在限制的时间内先救哪些人最能有价值，最大价值是多少？

题解：先使用bfs跑出每个人所需要的时间，然后把时间当作背包体积，把每个的价值就作为价值，直接跑01背包即可。

附上代码：

#include<bits/stdc++.h>using namespace std;const int maxs=1e4+50;
const int maxn=1e2+50;
const int maxf=1e2+50;
const int maxh=1e2+50;
const int maxw=1e2+50;
int Next[][2]={{0,1},{1,0},{0,-1},{-1,0}};int l,h,w,n,s;
int vol[maxn],val[maxn];
char mapp[maxf][maxh][maxw];
bool book[maxf][maxh][maxw];
int sec[maxf][maxh][maxw];
int dp[maxs];struct node{int f,r,c,w;node(int _f=0,int _r=0,int _c=0,int _w=0):f(_f),r(_r),c(_c),w(_w){}
};bool safe(int f,int r,int c)
{if(!book[f][r][c]&&mapp[f][r][c]!='X'&&f>=1&&f<=l&&r>=1&&r<=h&&c>=1&&c<=w){return true;}return false;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d%d%d%d",&l,&h,&w,&n,&s);for(int i=1;i<=l;i++){for(int j=1;j<=h;j++){scanf("%s",mapp[i][j]+1);}}memset(sec,0,sizeof(sec));int a,b,c,d;for(int i=0;i<n;i++){scanf("%d%d%d%d",&a,&b,&c,&d);sec[a][b][c]=d;}int bx=0,by=0;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){if(mapp[1][i][j]=='S'){bx=i,by=j;break;}}if(bx){break;}}memset(book,false,sizeof(book));node bb=node(1,bx,by,0);book[1][bx][by]=1;queue<node>q;while(!q.empty()){q.pop();}q.push(bb);int cnt=0;while(!q.empty()){node u=q.front();q.pop();for(int i=0;i<4;i++){int nf=u.f,nx=u.r+Next[i][0],ny=u.c+Next[i][1],nw=u.w+1;if(safe(nf,nx,ny)){book[nf][nx][ny]=true;q.push(node(nf,nx,ny,nw));if(sec[nf][nx][ny]){vol[cnt]=nw*3;val[cnt++]=sec[nf][nx][ny];}}}if(mapp[u.f][u.r][u.c]=='U'){int nf=u.f+1,nx=u.r,ny=u.c,nw=u.w+1;if(!book[nf][nx][ny]){book[nf][nx][ny]=true;q.push(node(nf,nx,ny,nw));if(sec[nf][nx][ny]){vol[cnt]=nw*3;val[cnt++]=sec[nf][nx][ny];}}}if(mapp[u.f][u.r][u.c]=='D'){int nf=u.f-1,nx=u.r,ny=u.c,nw=u.w+1;if(!book[nf][nx][ny]){book[nf][nx][ny]=true;q.push(node(nf,nx,ny,nw));if(sec[nf][nx][ny]){vol[cnt]=nw*3;val[cnt++]=sec[nf][nx][ny];}}}}memset(dp,0,sizeof(dp));for(int i=0;i<cnt;i++){for(int j=s;j>=vol[i];j--){dp[j]=max(dp[j],dp[j-vol[i]]+val[i]);}}printf("%d\n",dp[s]);}return 0;
}