第1题-最小距离和题目内容每天早晨环卫工人需要处理各个小区的生活垃圾每个小区的生活垃圾由一队坏卫工人负责运送到最近的垃圾回收站进行处理求将所有小区垃圾送到垃圾回收站的最小距离和。假设小区和垃圾回收站都在都在一个行 列的区域矩阵上相邻点的距离为只能上下左右移动;其中表示垃圾处理站表示小区表示空白区域表示障碍区域不可通行。区域内如果没有小区或者没有垃圾回收站则最小距离和返回。无法到达垃圾回收站的小区会单独处理不计入本次距离和中。计算所有小区垃圾送到垃圾回收站的最小距离和。输入描述第一行为两个数字和的和表示区域矩阵的行数和列数中间使用空格分隔和的范围均为。接下来的行表示一个的区域矩阵数组每行的元素间以空格分隔其中元素取值仅为(障碍区域)、(垃圾处理站)、(小区)、(空白区域)。输出描述一个整数表示所计算的最小距离和。样例1输入4 4 1 2 -1 1 2 0 2 0 2 2 -1 2 1 2 1 1输出11说明如图所示位置、、、、是小区位置、是垃圾站位置、是障碍无法通行个小区个垃圾站小区到垃圾站的最小路径是。对于位置的小区可以将垃圾运送到垃圾站、两者的距离是一样的。题解图示仅以到垃圾站进行说明。样例2输入2 3 0 -1 1 1 -1 2输出1说明图2如图所示位置、小区位置是垃圾站位置、是障碍无法通行个小区个垃圾站小区到垃圾站的最小路径是。思路广度优先搜索将所有垃圾站的距离初始化为0并加入队列中。用广度优先搜索算法逐层向外扩展并用一个额外数组记录到达每个点的最短距离。如果一个点有值说明某一个垃圾站离该点更近则不在使用当前点进行该方向的扩展。最后扫描所有小区累加它们的值即可。不可到达的小区值为0。代码Pythonfrom collections import deque def init(): n , m map(int , input().split()) a [list(map(int, input().split())) for _ in range(n)] return n, m, a def solve(n, m, a): b [[0] * m for _ in range(n)] q deque() # 初始化队列将所有 0 的位置加入队列 for i in range(n): for j in range(m): if a[i][j] 0: q.append((i, j, 0)) # (x, y, current_distance) dx [0, 0, -1, 1] dy [1, -1, 0, 0] while q: x, y, now q.popleft() for i in range(4): nx, ny x dx[i], y dy[i] # 检查边界 if nx 0 or nx n or ny 0 or ny m: continue if b[nx][ny] ! 0: continue if a[nx][ny] -1: continue b[nx][ny] now 1 q.append((nx, ny, now 1)) # 计算总和 total_sum 0 for i in range(n): for j in range(m): if a[i][j] 1: total_sum b[i][j] print(total_sum) if __name__ __main__: n, m, a init() solve(n, m, a)第2题-圣诞节礼盒题目内容圣诞节到了小塔的妈妈准备了很多圣诞礼盒礼盒大小不同小塔在玩堆盒子的游戏妈妈问小塔怎么堆盒子使得堆出的高度最高每个礼盒的大小由长、宽、高表示堆盒子的时候要求下面的盒子长、宽、高都必须大于上面的盒子不包含等于。请你帮助小塔一起堆出最高的一堆礼盒高度为堆出的礼盒的所有高度的总和。输入描述输入的第一行是礼盒的个数接下来输入行每行表示每个礼盒的长、宽、高。礼盒的数量不超过个每个盒子的长、宽、高取值范围为~。输出描述输出一行输出能堆出盒子的最高高度样例1输入4 1 1 1 2 3 4 3 6 7 4 5 6输出12说明选择、、个盒子堆出的高度最高样例2输入4 1 1 1 1 1 1 2 2 2 2 2 2输出3说明其中的一种选择方式为选择和两个盒子堆出的高度最高为思路动态规划将所有盒子按照长、宽、高的三个优先级进行从小到大的排序那么后面的盒子一定不可能放在前面盒子的上面。定义表示放上第个盒子所能达到的最大高度则有答案为代码C#include bits/stdc.h using namespace std; const int maxn1e310; int dp[maxn]; int n; struct node{ int l, w, h; }box[maxn]; int main(){ std::ios::sync_with_stdio(false); cinn; for(int i1;in;i){ cinbox[i].lbox[i].wbox[i].h; } sort(box1, boxn1, [](node a, node b){ if(a.l!b.l){ return a.lb.l; } if(a.w!b.w){ return a.wb.w; } return a.hb.h; }); int ans0; for(int i1;in;i){ dp[i]box[i].h; for(int j1;ji;j){ if(box[i].hbox[j].hbox[i].lbox[j].lbox[i].wbox[j].w){ dp[i]max(dp[i],dp[j]box[i].h); } } ans max(ans,dp[i]); } coutans; return 0; }其他语言见华为题库的题解区第3题-基站的盈利问题题目内容有个基站采用链式组网按照从左到右编码为到编号。已知定义“业务”概念为三元组(基站起始编号基站结束编号利润)意味着需要占据基站起始编号到基站结束编号的所有基站打通信号流可以获得对应利润。现在外部存在多个“业务需求待接纳但基站使用具有排他性也就是说一旦某一个业务占据某个基站其他业务不可以再使用此基站。那么接纳哪些业务需求可以使得利润最大化?输入描述第一行输入表示有个基站。取值范围第二行输入表示有组业务。,M取值范围接下来行每行输入三个整数 以空格隔开表示起始基站编号结束基站编号利润。取值范围输出描述输出只有一个整数表示获取的利润样例1输入5 2 1 5 4 2 4 8输出8说明样例2输入5 2 1 5 4 2 4 1输出4说明已经使用过到不能再使用的样例3输入20 6 1 6 1 3 10 2 10 12 3 11 12 2 12 15 2 13 18 1输出5说明我们可以这么选择业务选择到的基站获利选择到的基站获利选择到的基站获利最终获利也可以选择注意使用的基站不能重合思路动态规划对于处于位置处的一个可选基站其占据位置为利润为。那么如果要选择该基站上一个基站必须处于之前。定义表示终点在及以前的所有基站所能获得的最大利润有。其中。代码C#include bits/stdc.h using namespace std; const int maxn1e410; int n,m; vectorpairint,int a[maxn]; int f[maxn]; int main() { cinnm; for(int i1;im;i){ int l,r,c; cinlrc; a[r].push_back(make_pair(l,c)); } for(int i1;in;i){ f[i]f[i-1]; for(auto x:a[i]){ f[i] max(f[i], f[x.first - 1] x.second); } } coutf[n]; return 0; }学员喜报25秋招:8月29日机考通过