吃个奶酪吧
题目描述
房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0) 点处。
输入格式
第一行有一个整数，表示奶酪的数量 n。
第 2 到第 (n+1) 行，每行两个实数，第 (i+1) 行的实数分别表示第 i 块奶酪的横纵坐标 xi,yi。
输出格式
输出一行一个实数，表示要跑的最少距离，保留 2 位小数
这道题主播写了一个构造函数写个一个输入奶酪坐标的一个循环就尽力了，然后怎么想也想不出，一开始想的是计算他们每个点之间的距离 然后累加看，比较，最小的是哪个就输出哪个但是呢，我看了题解发现动态规划是做这道题的最佳解，因为主播没遇到过这种提第一次遇到，遇到最熟悉的就是爬楼梯但是感觉难度不在一个维度啊，用二进制数mask记录已经吃过的奶酪，dp[mask][i]表示已经吃完mask集合内奶酪，当前位于第i块奶酪时的最短行走距离。两点间使用欧几里得公式计算距离。初始化时，dp[1<<i][i]赋值为原点(0,0)到第i块奶酪的距离，其余状态初始化为无穷大。遍历全部状态，对每个状态，枚举当前所在奶酪i，再枚举上一个位置j。去掉i得到前驱状态，执行状态转移：dp[mask][i]=min(dp[mask][i],dp[pre][j]+dis(j,i))，用旧状态更新当前状态最小值。当mask=(1<<n)-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 颗流星会在时刻 Ti（0≤Ti≤1000）砸在坐标为 (Xi,Yi)(0≤Xi≤300，0≤Yi≤300) 的格子里。流星的力量会将它所在的格子，以及周围 4 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 0 开始行动，她只能在横纵坐标 X,Y≥0 的区域中，平行于坐标轴行动，每 1 个时刻中，她能移动到相邻的（一般是 4 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦，那么贝茜只能在 t 之前的时刻在这个格子里出现。 贝茜一开始在 (0,0)。
请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 −1。
输入格式
共 M+1 行，第 1 行输入一个整数 M，接下来的 M 行每行输入三个整数分别为 Xi,Yi,Ti。
输出格式
贝茜到达安全地点所需的最短时间，如果不可能，则为 −1。本题是 BFS 最短路问题，求贝茜逃到永久安全点的最短时间。流星砸落时会摧毁自身及上下左右四格，每个格子记录最早被摧毁的时刻，永远不会被砸到则记为无穷大。使用hurt数组存储每个格子被摧毁的最早时间，读入每一颗流星，更新落点和四邻格子的摧毁时间，保留最小值。采用队列实现 BFS，从原点(0,0)开始向外搜索，队列保存坐标与到达时间。取出队首节点，如果该格子永远不会被流星摧毁，直接输出当前时间结束程序。向四个方向拓展，新坐标不能为负数，没有访问过，并且到达该格子的时间必须小于格子被摧毁的时间，满足条件标记入队。队列为空代表无路可逃，输出-1。BFS 保证第一次搜到安全点就是最短时间。关键点：cur.t+1 < hurt[nx][ny]，下一秒到达，必须在格子被炸之前赶到。
题目背景
kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。
题目描述
这次期末考试，kkksc03 需要考 4 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1，B1,B2,…,Bs2，C1,C2,…,Cs3，D1,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 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,19 时，可得全部的组合与它们的和为：
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=29。
输入格式
第一行两个空格隔开的整数 n,k（1≤n≤20，k<n）。
第二行 n 个整数，分别为 x1,x2,⋯,xn（1≤xi≤5×106）。
输出格式
输出一个整数，表示种类数。
题目给定 n 个整数，从中选出恰好 k 个数进行相加，统计总和为素数的组合方案数量。\(n\le20\)，数据规模不大，可以用 DFS 暴力枚举所有选或不选的组合。使用深度优先搜索 DFS 进行组合枚举。dfs(pos,cnt,sum)中，pos代表当前处理到第几个数字，cnt代表已经选了多少个数，sum是已经选中数字的累加和。对当前数字有两种分支：选这个数，或者不选这个数。 递归终止条件：当选够 k 个数（cnt==k），判断累加和是否为素数，如果是则答案计数ans++；如果处理完所有数字还没选够 k 个，直接返回。素数判断函数isprime(x)，小于 2 直接判定不是素数；循环从 2 到sqrt（x)，若能整除说明不是素数，否则为素数。 主函数读入数据，从第 1 个位置开始 DFS，最后输出总方案数。
题目描述
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s 和苦度 b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物是只以水为配料的。
输入格式
第一行一个整数 n，表示可供选用的食材种类数。
接下来 n 行，每行 2 个整数 si 和 bi，表示第 i 种食材的酸度和苦度。
输出格式
一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
本题有 n 种配料，每种配料有酸度s和苦度b。选出至少一种配料，总酸度是选中配料酸度的乘积，总苦度是选中配料苦度的和，求酸度与苦度差值的绝对值的最小值。规模很小，使用 DFS 枚举每一种配料选或者不选。dfs(pos,mul,sum)中，pos表示当前处理第几种配料，mul记录总酸度乘积，sum记录总苦度累加和。两个分支：选取当前配料，更新乘积与累加和；不选取当前配料，参数保持不变。递归边界：处理完全部配料pos>n时，如果mul!=1说明已经选了至少一种配料，更新答案为min(ans,abs(mul‑sum))，直接返回。注意不能全部不选，全部不选时乘积为 1、苦度为 0，需要跳过该情况。dfs(pos+1,mul*s[pos],sum+b[pos])：选第pos种配料，酸度相乘，苦度相加。dfs(pos+1,mul,sum)：不选第pos种配料，数值不变。mul!=1用来排除一种配料都没选的非法情况