题目描述房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉问至少要跑多少距离老鼠一开始在 (0,0) 点处。输入格式第一行有一个整数表示奶酪的数量 n。第 2 到第 (n1) 行每行两个实数第 (i1) 行的实数分别表示第 i 块奶酪的横纵坐标 xi,yi。输出格式输出一行一个实数表示要跑的最少距离保留 2 位小数这道题主播写了一个构造函数写个一个输入奶酪坐标的一个循环就尽力了然后怎么想也想不出一开始想的是计算他们每个点之间的距离 然后累加看比较最小的是哪个就输出哪个但是呢我看了题解发现动态规划是做这道题的最佳解因为主播没遇到过这种提第一次遇到遇到最熟悉的就是爬楼梯但是感觉难度不在一个维度啊用二进制数mask记录已经吃过的奶酪dp[mask][i]表示已经吃完mask集合内奶酪当前位于第i块奶酪时的最短行走距离。两点间使用欧几里得公式计算距离。初始化时dp[1i][i]赋值为原点(0,0)到第i块奶酪的距离其余状态初始化为无穷大。遍历全部状态对每个状态枚举当前所在奶酪i再枚举上一个位置j。去掉i得到前驱状态执行状态转移dp[mask][i]min(dp[mask][i],dp[pre][j]dis(j,i))用旧状态更新当前状态最小值。当mask(1n)-1代表全部奶酪吃完遍历所有终点取dp最小值即为答案输出保留两位小数。这里又学到用二进制来代表已经吃完的奶酪和未吃完的奶酪这道题真是给我干力竭了兄弟题目描述给定一个 N×M 方格的迷宫迷宫里有 T 处障碍障碍处不可通过。在迷宫中移动有上下左右四种方式每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标每个方格最多经过一次问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数 N,M,T分别表示迷宫的长宽和障碍总数。第二行为四个正整数 SX,SY,FX,FY。SX,SY 代表起点坐标FX,FY 代表终点坐标。接下来 T 行每行两个正整数表示障碍点的坐标。输出格式输出从起点坐标到终点坐标的方案总数。这道题跟之前的题差不多用dfs递归回溯使用vis数组记录格子状态障碍与已经走过的格子标记为 true避免重复访问。设置方向数组dx、dy模拟上下左右四个移动方向。递归函数dfs(x,y)代表当前处在坐标(x,y)如果到达终点方案计数 ans 加一否则遍历四个方向判断新坐标没有越界、不是障碍、未曾访问。满足条件时标记该格子已访问向下递归搜索递归返回后执行回溯取消该格子标记方便其他路径复用该位置。主函数读入迷宫大小、障碍、起点终点先标记障碍起点打上访问标记调用 dfs 开始搜索最终输出总方案数。回溯的关键在于前进时标记递归结束撤销标记枚举所有可行路径。本题规模小暴力枚举全部路径即可通过无需动态规划题目描述贝茜听说一场特别的流星雨即将到来这些流星会撞向地球并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑发誓要找到一个安全的地方一个永远不会被流星摧毁的地方。如果将牧场放入一个直角坐标系中贝茜现在的位置是原点并且贝茜不能踏上一块被流星砸过的土地。根据预报一共有 M 颗流星 (1≤M≤50,000) 会坠落在农场上其中第 i 颗流星会在时刻 Ti0≤Ti≤1000砸在坐标为 (Xi,Yi)(0≤Xi≤3000≤Yi≤300) 的格子里。流星的力量会将它所在的格子以及周围 4 个相邻的格子都化为焦土当然贝茜也无法再在这些格子上行走。贝茜在时刻 0 开始行动她只能在横纵坐标 X,Y≥0 的区域中平行于坐标轴行动每 1 个时刻中她能移动到相邻的一般是 4 个格子中的任意一个当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦那么贝茜只能在 t 之前的时刻在这个格子里出现。 贝茜一开始在 (0,0)。请你计算一下贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 −1。输入格式共 M1 行第 1 行输入一个整数 M接下来的 M 行每行输入三个整数分别为 Xi,Yi,Ti。输出格式贝茜到达安全地点所需的最短时间如果不可能则为 −1。本题是 BFS 最短路问题求贝茜逃到永久安全点的最短时间。流星砸落时会摧毁自身及上下左右四格每个格子记录最早被摧毁的时刻永远不会被砸到则记为无穷大。使用hurt数组存储每个格子被摧毁的最早时间读入每一颗流星更新落点和四邻格子的摧毁时间保留最小值。采用队列实现 BFS从原点(0,0)开始向外搜索队列保存坐标与到达时间。取出队首节点如果该格子永远不会被流星摧毁直接输出当前时间结束程序。向四个方向拓展新坐标不能为负数没有访问过并且到达该格子的时间必须小于格子被摧毁的时间满足条件标记入队。队列为空代表无路可逃输出-1。BFS 保证第一次搜到安全点就是最短时间。关键点cur.t1 hurt[nx][ny]下一秒到达必须在格子被炸之前赶到。题目背景kkksc03 的大学生活非常的颓废平时根本不学习。但是临近期末考试他必须要开始抱佛脚以求不挂科。题目描述这次期末考试kkksc03 需要考 4 科。因此要开始刷习题集每科都有一个习题集分别有 s1,s2,s3,s4 道题目完成每道题目需要一些时间可能不等A1,A2,…,As1B1,B2,…,Bs2C1,C2,…,Cs3D1,D2,…,Ds4。kkksc03 有一个能力他的左右两个大脑可以同时计算 2 道不同的题目但是仅限于同一科。因此kkksc03 必须一科一科的复习。由于 kkksc03 还急着去处理洛谷的 bug因此他希望尽快把事情做完所以他希望知道能够完成复习的最短时间。输入格式本题包含 5 行数据第 1 行为四个正整数 s1,s2,s3,s4。第 2 行为 A1,A2,…,As1 共 s1 个数表示第一科习题集每道题目所消耗的时间。第 3 行为 B1,B2,…,Bs2 共 s2 个数。第 4 行为 C1,C2,…,Cs3 共 s3 个数。第 5 行为 D1,D2,…,Ds4 共 s4 个数意思均同上。输出格式输出一行为复习完毕最短时间。这道题主播在贪心的是做过但是错了但是做到广搜能做本题需要完成四科习题同一科的题目可以分配给左右两个大脑并行计算每道题目完整交给其中一个大脑一科的完成时间取左右大脑耗时的较大值四科依次完成求复习全部科目的最短总时间。该问题本质为子集和问题属于 0‑1 背包模型四科互相独立分科求解再累加结果。对于某一科先计算该科所有题目总时间total目标挑选一部分题目给其中一个大脑使其总时长尽可能接近total/2让两个大脑时间差距最小。定义布尔数组dp[j]表示能否选出若干题目凑出j的时间采用 0‑1 背包倒序遍历更新状态。从total/2向下查找最大可以凑出的时间best该科最短耗时为total‑best把四科结果相加即为答案。我最初使用贪心思路读入一道题就直接加到当前总和更小的一侧。贪心只能做到局部最优不能保证全局最优部分样例分配会得到错误结果造成全部测试点 WA。子集划分问题不能简单贪心需要用 0‑1 背包或者 DFS 枚举全部分配方案才能得到最优解。已知 n 个整数 x1,x2,⋯,xn以及 1 个整数 kkn。从 n 个整数中任选 k 个整数相加可分别得到一系列的和。例如当 n4k34 个整数分别为 3,7,12,19 时可得全部的组合与它们的和为37122237192971219383121934现在要求你计算出和为素数共有多少种。例如上例只有一种的和为素数371929。输入格式第一行两个空格隔开的整数 n,k1≤n≤20kn。第二行 n 个整数分别为 x1,x2,⋯,xn1≤xi≤5×106。输出格式输出一个整数表示种类数。题目给定 n 个整数从中选出恰好 k 个数进行相加统计总和为素数的组合方案数量。\(n\le20\)数据规模不大可以用 DFS 暴力枚举所有选或不选的组合。使用深度优先搜索 DFS 进行组合枚举。dfs(pos,cnt,sum)中pos代表当前处理到第几个数字cnt代表已经选了多少个数sum是已经选中数字的累加和。对当前数字有两种分支选这个数或者不选这个数。 递归终止条件当选够 k 个数cntk判断累加和是否为素数如果是则答案计数ans如果处理完所有数字还没选够 k 个直接返回。素数判断函数isprime(x)小于 2 直接判定不是素数循环从 2 到sqrtx)若能整除说明不是素数否则为素数。 主函数读入数据从第 1 个位置开始 DFS最后输出总方案数。题目描述Perket 是一种流行的美食。为了做好 Perket厨师必须谨慎选择食材以在保持传统风味的同时尽可能获得最全面的味道。你有 n 种可支配的配料。对于每一种配料我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时总的酸度为每一种配料的酸度总乘积总的苦度为每一种配料的苦度的总和。众所周知美食应该做到口感适中所以我们希望选取配料以使得酸度和苦度的绝对差最小。另外我们必须添加至少一种配料因为没有任何食物是只以水为配料的。输入格式第一行一个整数 n表示可供选用的食材种类数。接下来 n 行每行 2 个整数 si 和 bi表示第 i 种食材的酸度和苦度。输出格式一行一个整数表示可能的总酸度和总苦度的最小绝对差。本题有 n 种配料每种配料有酸度s和苦度b。选出至少一种配料总酸度是选中配料酸度的乘积总苦度是选中配料苦度的和求酸度与苦度差值的绝对值的最小值。规模很小使用 DFS 枚举每一种配料选或者不选。dfs(pos,mul,sum)中pos表示当前处理第几种配料mul记录总酸度乘积sum记录总苦度累加和。两个分支选取当前配料更新乘积与累加和不选取当前配料参数保持不变。递归边界处理完全部配料posn时如果mul!1说明已经选了至少一种配料更新答案为min(ans,abs(mul‑sum))直接返回。注意不能全部不选全部不选时乘积为 1、苦度为 0需要跳过该情况。dfs(pos1,mul*s[pos],sumb[pos])选第pos种配料酸度相乘苦度相加。dfs(pos1,mul,sum)不选第pos种配料数值不变。mul!1用来排除一种配料都没选的非法情况
题目描述房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉问至少要跑多少距离老鼠一开始在 (0,0) 点处。输入格式第一行有一个整数表示奶酪的数量 n。第 2 到第 (n1) 行每行两个实数第 (i1) 行的实数分别表示第 i 块奶酪的横纵坐标 xi,yi。输出格式输出一行一个实数表示要跑的最少距离保留 2 位小数这道题主播写了一个构造函数写个一个输入奶酪坐标的一个循环就尽力了然后怎么想也想不出一开始想的是计算他们每个点之间的距离 然后累加看比较最小的是哪个就输出哪个但是呢我看了题解发现动态规划是做这道题的最佳解因为主播没遇到过这种提第一次遇到遇到最熟悉的就是爬楼梯但是感觉难度不在一个维度啊用二进制数mask记录已经吃过的奶酪dp[mask][i]表示已经吃完mask集合内奶酪当前位于第i块奶酪时的最短行走距离。两点间使用欧几里得公式计算距离。初始化时dp[1i][i]赋值为原点(0,0)到第i块奶酪的距离其余状态初始化为无穷大。遍历全部状态对每个状态枚举当前所在奶酪i再枚举上一个位置j。去掉i得到前驱状态执行状态转移dp[mask][i]min(dp[mask][i],dp[pre][j]dis(j,i))用旧状态更新当前状态最小值。当mask(1n)-1代表全部奶酪吃完遍历所有终点取dp最小值即为答案输出保留两位小数。这里又学到用二进制来代表已经吃完的奶酪和未吃完的奶酪这道题真是给我干力竭了兄弟题目描述给定一个 N×M 方格的迷宫迷宫里有 T 处障碍障碍处不可通过。在迷宫中移动有上下左右四种方式每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标每个方格最多经过一次问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数 N,M,T分别表示迷宫的长宽和障碍总数。第二行为四个正整数 SX,SY,FX,FY。SX,SY 代表起点坐标FX,FY 代表终点坐标。接下来 T 行每行两个正整数表示障碍点的坐标。输出格式输出从起点坐标到终点坐标的方案总数。这道题跟之前的题差不多用dfs递归回溯使用vis数组记录格子状态障碍与已经走过的格子标记为 true避免重复访问。设置方向数组dx、dy模拟上下左右四个移动方向。递归函数dfs(x,y)代表当前处在坐标(x,y)如果到达终点方案计数 ans 加一否则遍历四个方向判断新坐标没有越界、不是障碍、未曾访问。满足条件时标记该格子已访问向下递归搜索递归返回后执行回溯取消该格子标记方便其他路径复用该位置。主函数读入迷宫大小、障碍、起点终点先标记障碍起点打上访问标记调用 dfs 开始搜索最终输出总方案数。回溯的关键在于前进时标记递归结束撤销标记枚举所有可行路径。本题规模小暴力枚举全部路径即可通过无需动态规划题目描述贝茜听说一场特别的流星雨即将到来这些流星会撞向地球并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑发誓要找到一个安全的地方一个永远不会被流星摧毁的地方。如果将牧场放入一个直角坐标系中贝茜现在的位置是原点并且贝茜不能踏上一块被流星砸过的土地。根据预报一共有 M 颗流星 (1≤M≤50,000) 会坠落在农场上其中第 i 颗流星会在时刻 Ti0≤Ti≤1000砸在坐标为 (Xi,Yi)(0≤Xi≤3000≤Yi≤300) 的格子里。流星的力量会将它所在的格子以及周围 4 个相邻的格子都化为焦土当然贝茜也无法再在这些格子上行走。贝茜在时刻 0 开始行动她只能在横纵坐标 X,Y≥0 的区域中平行于坐标轴行动每 1 个时刻中她能移动到相邻的一般是 4 个格子中的任意一个当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦那么贝茜只能在 t 之前的时刻在这个格子里出现。 贝茜一开始在 (0,0)。请你计算一下贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 −1。输入格式共 M1 行第 1 行输入一个整数 M接下来的 M 行每行输入三个整数分别为 Xi,Yi,Ti。输出格式贝茜到达安全地点所需的最短时间如果不可能则为 −1。本题是 BFS 最短路问题求贝茜逃到永久安全点的最短时间。流星砸落时会摧毁自身及上下左右四格每个格子记录最早被摧毁的时刻永远不会被砸到则记为无穷大。使用hurt数组存储每个格子被摧毁的最早时间读入每一颗流星更新落点和四邻格子的摧毁时间保留最小值。采用队列实现 BFS从原点(0,0)开始向外搜索队列保存坐标与到达时间。取出队首节点如果该格子永远不会被流星摧毁直接输出当前时间结束程序。向四个方向拓展新坐标不能为负数没有访问过并且到达该格子的时间必须小于格子被摧毁的时间满足条件标记入队。队列为空代表无路可逃输出-1。BFS 保证第一次搜到安全点就是最短时间。关键点cur.t1 hurt[nx][ny]下一秒到达必须在格子被炸之前赶到。题目背景kkksc03 的大学生活非常的颓废平时根本不学习。但是临近期末考试他必须要开始抱佛脚以求不挂科。题目描述这次期末考试kkksc03 需要考 4 科。因此要开始刷习题集每科都有一个习题集分别有 s1,s2,s3,s4 道题目完成每道题目需要一些时间可能不等A1,A2,…,As1B1,B2,…,Bs2C1,C2,…,Cs3D1,D2,…,Ds4。kkksc03 有一个能力他的左右两个大脑可以同时计算 2 道不同的题目但是仅限于同一科。因此kkksc03 必须一科一科的复习。由于 kkksc03 还急着去处理洛谷的 bug因此他希望尽快把事情做完所以他希望知道能够完成复习的最短时间。输入格式本题包含 5 行数据第 1 行为四个正整数 s1,s2,s3,s4。第 2 行为 A1,A2,…,As1 共 s1 个数表示第一科习题集每道题目所消耗的时间。第 3 行为 B1,B2,…,Bs2 共 s2 个数。第 4 行为 C1,C2,…,Cs3 共 s3 个数。第 5 行为 D1,D2,…,Ds4 共 s4 个数意思均同上。输出格式输出一行为复习完毕最短时间。这道题主播在贪心的是做过但是错了但是做到广搜能做本题需要完成四科习题同一科的题目可以分配给左右两个大脑并行计算每道题目完整交给其中一个大脑一科的完成时间取左右大脑耗时的较大值四科依次完成求复习全部科目的最短总时间。该问题本质为子集和问题属于 0‑1 背包模型四科互相独立分科求解再累加结果。对于某一科先计算该科所有题目总时间total目标挑选一部分题目给其中一个大脑使其总时长尽可能接近total/2让两个大脑时间差距最小。定义布尔数组dp[j]表示能否选出若干题目凑出j的时间采用 0‑1 背包倒序遍历更新状态。从total/2向下查找最大可以凑出的时间best该科最短耗时为total‑best把四科结果相加即为答案。我最初使用贪心思路读入一道题就直接加到当前总和更小的一侧。贪心只能做到局部最优不能保证全局最优部分样例分配会得到错误结果造成全部测试点 WA。子集划分问题不能简单贪心需要用 0‑1 背包或者 DFS 枚举全部分配方案才能得到最优解。已知 n 个整数 x1,x2,⋯,xn以及 1 个整数 kkn。从 n 个整数中任选 k 个整数相加可分别得到一系列的和。例如当 n4k34 个整数分别为 3,7,12,19 时可得全部的组合与它们的和为37122237192971219383121934现在要求你计算出和为素数共有多少种。例如上例只有一种的和为素数371929。输入格式第一行两个空格隔开的整数 n,k1≤n≤20kn。第二行 n 个整数分别为 x1,x2,⋯,xn1≤xi≤5×106。输出格式输出一个整数表示种类数。题目给定 n 个整数从中选出恰好 k 个数进行相加统计总和为素数的组合方案数量。\(n\le20\)数据规模不大可以用 DFS 暴力枚举所有选或不选的组合。使用深度优先搜索 DFS 进行组合枚举。dfs(pos,cnt,sum)中pos代表当前处理到第几个数字cnt代表已经选了多少个数sum是已经选中数字的累加和。对当前数字有两种分支选这个数或者不选这个数。 递归终止条件当选够 k 个数cntk判断累加和是否为素数如果是则答案计数ans如果处理完所有数字还没选够 k 个直接返回。素数判断函数isprime(x)小于 2 直接判定不是素数循环从 2 到sqrtx)若能整除说明不是素数否则为素数。 主函数读入数据从第 1 个位置开始 DFS最后输出总方案数。题目描述Perket 是一种流行的美食。为了做好 Perket厨师必须谨慎选择食材以在保持传统风味的同时尽可能获得最全面的味道。你有 n 种可支配的配料。对于每一种配料我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时总的酸度为每一种配料的酸度总乘积总的苦度为每一种配料的苦度的总和。众所周知美食应该做到口感适中所以我们希望选取配料以使得酸度和苦度的绝对差最小。另外我们必须添加至少一种配料因为没有任何食物是只以水为配料的。输入格式第一行一个整数 n表示可供选用的食材种类数。接下来 n 行每行 2 个整数 si 和 bi表示第 i 种食材的酸度和苦度。输出格式一行一个整数表示可能的总酸度和总苦度的最小绝对差。本题有 n 种配料每种配料有酸度s和苦度b。选出至少一种配料总酸度是选中配料酸度的乘积总苦度是选中配料苦度的和求酸度与苦度差值的绝对值的最小值。规模很小使用 DFS 枚举每一种配料选或者不选。dfs(pos,mul,sum)中pos表示当前处理第几种配料mul记录总酸度乘积sum记录总苦度累加和。两个分支选取当前配料更新乘积与累加和不选取当前配料参数保持不变。递归边界处理完全部配料posn时如果mul!1说明已经选了至少一种配料更新答案为min(ans,abs(mul‑sum))直接返回。注意不能全部不选全部不选时乘积为 1、苦度为 0需要跳过该情况。dfs(pos1,mul*s[pos],sumb[pos])选第pos种配料酸度相乘苦度相加。dfs(pos1,mul,sum)不选第pos种配料数值不变。mul!1用来排除一种配料都没选的非法情况
