自己制作一个网站需要什么软件,全景网站是怎么做的,网站建设源代码上传,wordpress导航分类怎么添加new目录 一、DFS剪支
二、例题
P2942 数字王国之军训军队 P3075 特殊的多边形
三、记忆化搜索
四、例题
例题 P3820 混境之地
P216 地宫取宝 一、DFS剪支 在搜索过程中#xff0c;如果需要完全遍历所有情况可能需要很多时间在搜索到某种状态时#xff0c;根据当前状态判断…目录 一、DFS剪支
二、例题
P2942 数字王国之军训军队 P3075 特殊的多边形
三、记忆化搜索
四、例题
例题 P3820 混境之地
P216 地宫取宝 一、DFS剪支 在搜索过程中如果需要完全遍历所有情况可能需要很多时间在搜索到某种状态时根据当前状态判断出后续无解则该状态无需继续深入搜索例如给定N个正整数求出有多少个子集之和小于等于K。在搜索过程中当前选择的数字和已经超过K则不需要继续搜索。可行性剪枝当前状态和题意不符并且往后的所有情况和题意都不符那么就可以进行剪枝。最优性剪枝在搜索过程中当前状态已经不如已经找到的最优解也可以剪枝不需要继续搜索。 二、例题
P2942 数字王国之军训军队 数字王国开学了它们也和我们人类一样有开学前的军训现在一共有 n 名学生每个学生有自己的一个名字 ai数字王国里的名字就是一个正整数注意学生们可能出现重名的情况此时叛逆教官来看了之后感觉十分别扭决定将学生重新分队。 排队规则为将学生分成若干队每队里面至少一个学生且每队里面学生的名字不能出现倍数关系注意名字相同也算是倍数关系。 现在请你帮忙算算最少可以分成几队 例有 4 名学生 (2,3,4,4)最少可以分成 (2,3)、(4)、(4) 共 3 队。 输入格式 第一行包含一个正整数 n表示学生数量。 第二行包含 n 个由空格隔开的整数第 i 个整数表示第 i 个学生的名字 ai。 输出格式 输出共 1 行包含一个整数表示最少可以分成几队。 DFS 搜索枚举每个学生分到每个组内
可行性剪枝要满足题目条件
最优性剪枝判断当前状态是否比 ans 更劣 def check(x,group):for y in group:if x%y 0 or y%x0:return Falsereturn Truedef dfs(depth):if depthn:global answeranswermin(answer,len(Groups))returnfor every_group in Groups:if check(a[depth],every_group):every_group.append(a[depth])dfs(depth1)every_group.pop()Groups.append([a[depth]])dfs(depth1)Groups.pop()nint(input())
alist(map(int,input().split()))
Groups[]
answern
dfs(0)
print(answer)
# 判断x能否加入group组
def check(x, group):# 要保证不能存在倍数关系for y in group:if x % y 0 or y % x 0:return Falsereturn True# depth表示当前为第depth个学生
def dfs(depth):global ans# 最优性剪枝当前已经比ans大说明该策略不可行if len(Groups) ans:returnif depth n:ans min(len(Groups), ans)returnfor each_group in Groups:# 枚举第depth个学生能否加入当前组each_group# 剪枝必须满足题意if check(a[depth], each_group):each_group.append(a[depth])dfs(depth 1)each_group.pop()# 单独作为一组将 a[depth] 作为一个新的分组添加即 Groups.append([a[depth]])Groups.append([a[depth]])dfs(depth 1)Groups.pop()n int(input())
a list(map(int, input().split()))
# ans表示最少能分多少队
ans n# Groups表示分组情况
Groups []
dfs(0)
print(ans) P3075 特殊的多边形 假设一个 n 边形 n 条边为 a1,a2,a3,⋯,an定义该 n 边形的值 va1×a2×a3×⋯×an。 定义两个 n 边形不同是指至少有一条边的长度在一个 n 边形中有使用而另一个 n 边形没有用到如 n 边形 (3,4,5,6)和 (3,5,4,6) 是两个相同的 n 边形(3,4,5,6)和 (4,5,6,7) 是两个不相同的 n 边形。 现在有 t 和 n表示 t 个询问并且询问的是 n 边形每个询问给定一个区间 [l,r]问有多少个 n 边形要求该 n 边形自己的 n 条边的长度互不相同的值在该区间范围内。 输入格式 第一行包含两个正整数 t、n表示有 t 个询问询问的是 n 边形。 接下来 t 行每行有两个空格隔开的正整数 l、r表示询问区间 [l,r]。 输出格式 输出共 t 行第 i行对应第 i 个查询的 n 边形个数。 先考虑简单版乘积为 v 有多少种 n 边形 DFS 处理出所有乘积对应的所有可能 维护一个递增的边长序列唯一性 枚举第 i 边的长度最小最大范围剪枝 最终 check 是否满足 N 边形 最小的 N - 1 条边之和大于第 N 边 预处理前缀和 O(1)查询答案 import os
import sys# 请在此输入您的代码
def dfs(depth, last_val, tot, mul)::param depth: 第depth条边长:param last_val: 上一边长长度:param tot: 累计和:param mul: 累计乘积if depth n:# 前n-1条边之和大于第n条边if tot - path[-1] path[-1]:ans[mul] 1returnfor i in range(last_val 1, 100001):# 最优性剪枝, 后续还有n-depth个数字, 每个数字都要i# 累计乘积要不超过100000: mul * (i ** (n - depth))if mul * (i ** (n - depth)) 100000:breakpath.append(i)dfs(depth 1, i, tot i, mul * i)path.pop()t, n map(int, input().split())
ans [0] * 100001
path []
dfs(0, 0, 0, 1)for i in range(1, 100001):ans[i] ans[i - 1]
for _ in range(t):l, r map(int, input().split())print(ans[r] - ans[l - 1]) 三、记忆化搜索 记忆化通过记录已经遍历过的状态的信息从而避免对同一状态重复遍历的搜索实现方式。记忆化dfs额外字典 如果先前已经搜索过直接查字典返回字典中结果如果先前没有搜索过继续搜索最终将该状态结果记录到字典中 斐波那契数列设F[0] 1, F[1] 1, F[n] F[n - 1] F[n - 2]求F[n]结果对1e9 7取模。 0 n 10000样例输入 5000样例输出 976496506 def f(n):if n0 or n1:return 1return (f(n-1)f(n-2))%(1e97)
nint(input())
print(f(n))
# 直接递归存在大量重复计算
计算 F(5) 时要先算 F(4) 和 F(3)算 F(4) 又需算 F(3) 和 F(2)这里 F(3) 就被重复计算了。随着 n 增大像 F(2)、F(3) 这类中间结果会被反复多次计算导致时间复杂度呈指数级增长效率极低。 每次搜索时将当前状态答案记录到字典中后续搜索直接返回结果 import sys
sys.setrecursionlimit(100000)# 记忆化1
dic{0:1,1:1}
def f(n):if n in dic.keys():return dic[n]dic[n](f(n-1)f(n-2))%1000000007return dic[n]
nint(input())
print(f(n))from functools import lru_cache#记忆化搜索2
lru_cache(maxsizeNone) from functools import lru_cache# 记忆化2
lru_cache(maxsizeNone)
def f(n):if n0 or n1:return 1return f(n-1)f(n-2)
nint(input())
print(f(n)) 四、例题
例题 P3820 混境之地 小蓝有一天误入了一个混境之地。 好消息是他误打误撞拿到了一张地图并从中获取到以下信息 混境之地是一个 n⋅m 大小的矩阵其中第 i 行第 j 列的的点 hij 表示第 i 行第 j 列的高度。 他现在所在位置的坐标为 (A,B) 而这个混境之地出口的坐标为 (C,D) 当站在出口时即表示可以逃离混境之地。 小蓝有一个喷气背包使用时可以原地升高 k 个单位高度。 坏消息是 由于小蓝的体力透支所以只可以往低于当前高度的方向走。 喷漆背包燃料不足只可以最后使用一次。 小蓝可以往上下左右四个方向行走不消耗能量。 小蓝想知道他能否逃离这个混境之地如果可以逃离这里输入 Yes 反之输出 No 。 输入格式 第 1 行输入三个正整数 n,m 和 k n,m 表示混境之地的大小 k 表示使用一次喷气背包可以升高的高度。 第 2 行输入四个正整数 A,B,C,D 表示小蓝当前所在位置的坐标以及混境之地出口的坐标。 第 3 行至第 n2 行每行 m 个整数表示混境之地不同位置的高度。 输出格式 输出数据共一行一个字符串 若小蓝可以逃离混境之地则输出 Yes 。 若小蓝无法逃离混境之地则输出 No 。 走到(x,y)z表示是否使用喷气背包
当x,y,z固定时具有唯一解因此可以使用记忆化搜索
时间复杂度x,y,z三元组数量1000*1000*2
from functools import lru_cache#记忆化搜索2
lru_cache(maxsizeNone)
def dfs(x, y, z):# print(x, y, z)# 当前处于(x,y), z表示是否使用喷气背包# 如果能逃离, 返回True, 否则返回Falseif x C - 1 and y D - 1:return True#没走到终点四个方向判断for i in range(4):xx, yy x dir[i][0], y dir[i][1]#不能越界if xx 0 or xx n or yy 0 or yy m:continue#新坐标比旧坐标低走到新坐标xx,yy)if Map[xx][yy] Map[x][y]:if dfs(xx, yy, z):return True#在x,y)处使用喷气背包elif Map[xx][yy] Map[x][y] k and z False:if dfs(xx, yy, True):return Truereturn False# 四个方向
dir [(1, 0), (0, 1), (-1, 0), (0, -1)]
n, m, k map(int, input().split())
A, B, C, D map(int, input().split())
Map []
for i in range(n):Map.append(list(map(int, input().split())))
if dfs(A - 1, B - 1, False):print(Yes)
else:print(No) P216 地宫取宝 X 国王有一个地宫宝库。是 n×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角出口在右下角。 小明被带到地宫的入口国王要求他只能向右或向下行走。 走过某个格子时如果那个格子中的宝贝价值比小明手中任意宝贝价值都大小明就可以拿起它当然也可以不拿。 当小明走到出口时如果他手中的宝贝恰好是 k 件则这些宝贝就可以送给小明。 请你帮小明算一算在给定的局面下他有多少种不同的行动方案能获得这 k 件宝贝。 输入描述 输入一行 3 个整数用空格分开n,m,k (1≤n,m≤50,1≤k≤12)。 接下来有 n 行数据每行有m 个整数 Ci (0≤Ci≤12) 代表这个格子上的宝物的价值。 输出描述 要求输出一个整数表示正好取 k 个宝贝的行动方案数。该数字可能很大输出它对 10^97 取模的结果。 从(x,y)出发先前已经有宝物z件已有的最大宝物价值为w的方案数记为dfs(x,y,z,w)
只要确定四元组就确定当前的方案数
答案dfs(1,1,0,-1)
最终点dfs(n,m,z,?) or dfs(n,m,z - 1,?)
(x,y)处可选可不选然后可以往右走或者往下走
from functools import lru_cachelru_cache(maxsizeNone)
def dfs(x, y, z, w):#从(x,y)出发先前已有z件宝物已有宝物最大价值为w#走到终点if x n and y m:#当前不需要选择if z k:return 1#当前需要选择if z k - 1:if w a[x][y]:return 1#其他情况均为0return 0ans 0#遍历两个方向for delta_x, delta_y in [(1, 0), (0, 1)]:xx, yy x delta_x, y delta_yif xx n and yy m:# 当前不选择ans dfs(xx, yy, z, w)# 当前选择if w a[x][y]:ans dfs(xx, yy, z 1, a[x][y])return ans % 1000000007n, m, k map(int, input().split())
a [[0]*(m1)]
for i in range(n):a.append([0] list(map(int, input().split())))
print(dfs(1, 1, 0, -1))
