wordpress 鼠标悬停,google seo是什么,wordpress固定链,彩票网站平台欢迎交流学习~~ 专栏#xff1a; 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列#xff1a; #x1f3c6; Python | 蓝桥杯进阶第一卷——字符串 #x1f50e; Python | 蓝桥杯进阶第二卷——贪心 #x1f49d; Python | 蓝桥杯进阶第三卷——动态规划 ✈️ Python | 蓝桥杯进阶… 欢迎交流学习~~ 专栏 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列 Python | 蓝桥杯进阶第一卷——字符串 Python | 蓝桥杯进阶第二卷——贪心 Python | 蓝桥杯进阶第三卷——动态规划 ✈️ Python | 蓝桥杯进阶第四卷——图论 Python | 蓝桥杯进阶第五卷——数论 Python | 蓝桥杯进阶第六卷——搜索 Python|蓝桥杯进阶第三卷——动态规划 能量项链 夺宝奇兵 和最大子序列 超级玛丽 2^k进制数能量项链
题目 时间限制 1s
内存限制 128MB
题目描述 在Mars星球上每个Mars人都随身佩带着一串能量项链。在项链上有 N 颗能量珠。能量珠是一颗有头标记与尾标记的珠子这些标记对应着某个正整数。并且对于相邻的两颗珠子前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样通过吸盘吸盘是Mars人吸收能量的一种器官的作用这两颗珠子才能聚合成一颗珠子同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 m尾标记为 r后一颗能量珠的头标记为 r尾标记为 n则聚合后释放的能量为 m*r*nMars单位新产生的珠子的头标记为 m 尾标记为 n。 需要时Mars人就用吸盘夹住相邻的两颗珠子通过聚合得到能量直到项链上只剩下一颗珠子为止。显然不同的聚合顺序得到的总能量是不同的请你设计一个聚合顺序使一串项链释放出的总能量最大。 例如设 N44 颗珠子的头标记与尾标记依次为 (23) (35) (510) (102)。我们用记号 ◎ 表示两颗珠子的聚合操作(j◎k) 表示第 jk两颗珠子聚合后所释放的能量。则第 4、1 两颗珠子聚合后释放的能量为 (4◎1)10*2*360。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4◎1)◎2)◎310*2*310*3*510*5*10710。
输入描述 第一行是一个正整数 N4≤N≤100表示项链上珠子的个数。 第二行是 N 个用空格隔开的正整数所有的数均不超过 1000。第 i 个数为第 i 颗珠子的头标记1≤i≤N当 iN 时第 i 颗珠子的尾标记应该等于第 i1 颗珠子的头标记。第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。 至于珠子的顺序你可以这样确定将项链放到桌面上不要出现交叉随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序。
输出描述 只有一行是一个正整数 E(E ≤ 2.1*10^9)为一个最优聚合顺序所释放的总能量
样例输入
4
2 3 5 10样例输出 710 解题思路 针对动态规划类的题目我们通常采取以下思路 确定 dp 数组以及下标的含义确定递推公式初始化 dp 数组确定遍历顺序 接下来的题目我们都会按照这个思路。 确定 dp 数组及其下标的含义 dp[i][j] 表示第 i 颗珠子到第 j 颗珠子聚合成一颗珠子后所释放的最大能量。
确定递推公式 dp[i][j] max(dp[i][k] dp[k1][j] nums[i]*nums[k1]*nums[j1]), i≤kji\leq k ji≤kj, kkk 为断点 这里的 nums[i] 表示第 i 颗珠子的头标记但注意项链为环状我们可以将链状结构复制一份到后方同时在末尾再加上第1颗珠子的头标记比如样例中的 2, 3, 5, 10经过处理后是 nums[2, 3, 5, 10, 2, 3, 5, 10, 2]. 注意从第 k 个位置断开i ~ k 已经聚合成了一个珠子且 k1 ~ j 也已经聚合成了一个珠子这个在状态转移的过程中已经处理好了左右两个珠子聚合得到的能量为 nums[i]*nums[k1]*nums[j1] 初始化 dp 数组 都初始化为0即可。
确定遍历顺序 顺序遍历即可。 参考代码
n int(input())
nums list(map(int, input().split())) * 2
nums.append(nums[0])
dp [[0 for j in range(2*n)] for i in range(2*n)]
res 0# 递推
# 枚举区间长度
for length in range(1, n):# 枚举区间起点for i in range(2*n):# 计算区间终点j i length# 区间终点超出索引退出if j 2*n:break# 枚举区间断点for k in range(i, j):# 状态转移dp[i][j] max(dp[i][j], dp[i][k]dp[k1][j]nums[i]*nums[k1]*nums[j1])# 计算res最大值res max(res, dp[i][j])print(res)夺宝奇兵
题目 时间限制 1s
内存限制 128MB
题目描述 在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?每次只能直上或左上 在上图所示例子中,按照 5- 7- 8- 3- 7 的顺序,将得到最大值 30.
输入描述 第一行正整数 N(100 N 1),表示山的高度 接下来有 N 行非负整数,第 i 行有 i 个整数 (1 i N),表示山的第 i 层上从左到右每条路上的珠宝数目。
输出描述 一个整数,表示从山底到山顶的所能得到的珠宝的最大数目.
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5样例输出 30 解题思路
确定 dp 数组及其下标的含义 dp[i][j] 表示位置 i,j 对应的珠宝最大数目。
确定递推公式 dp[i][j] max(dp[i-1][j] cell[i][j], dp[i-1][j-1] cell[i][j])
初始化 dp 数组 都初始化为0即可。
确定遍历顺序 从上往下遍历即可。 参考代码
n int(input())
# cell 为每个位置的珠宝数目
cell []
for i in range(n):cell.append(list(map(int, input().split())))
# dp[i][j] 表示位置 i,j 对应的珠宝最大数目
dp [[0 for j in range(n)] for i in range(n)]
dp[0][0] cell[0][0]
# 从上往下遍历
for i in range(n):for j in range(i1):dp[i][j] max(dp[i-1][j] cell[i][j], dp[i-1][j-1] cell[i][j])# 最后一层的最大值
res max(dp[-1])
print(res)和最大子序列
题目 时间限制 1s
内存限制 128MB
题目描述 对于一个给定的长度为 N 的整数序列 A它的“子序列”的定义是A 中非空的一段连续的元素整数。你要完成的任务是在所有可能的子序列中找到一个子序列该子序列中所有元素的和是最大的跟其他所有子序列相比。程序要求你输出这个最大值。
输入描述 输入文件的第一行包含一个整数 N第二行包含 N 个整数表示 A。 其中 1 N 100000 -10000 A[i] 10000
输出描述 输出仅包含一个整数表示你算出的答案。
样例输入
5
3 -2 3 -5 4样例输出 4 解题思路 确定 dp 数组及其下标的含义 dp[i] 表示序列 nums[:i1] 的子序列的最大和。
确定递推公式 dp[i] max(dp[i-1]nums[i], nums[i])
初始化 dp 数组 初始化为 nums[0] 即可。
确定遍历顺序 顺序遍历即可。 参考代码
n int(input())
nums list(map(int, input().split()))
print(nums[:1])
# dp[i] 表示序列 nums[:i1] 的子序列的最大和
dp [nums[0] for i in range(n)]
for i in range(1, len(nums)):dp[i] max(dp[i-1]nums[i], nums[i])
print(max(dp))超级玛丽
题目 时间限制 1s
内存限制 128MB
题目描述 大家都知道 超级玛丽 是一个很善于跳跃的探险家他的拿手好戏是跳跃但它一次只能向前跳一步或两步。有一次他要经过一条长为 n 的羊肠小道小道中有 m 个陷阱这些陷阱都位于整数位置分别是 a1,a2,....,ama1,a2,...., ama1,a2,....,am陷入其中则必死无疑。显然如果有两个挨着的陷阱则玛丽是无论如何也跳过不去的。 现在给出小道的长度 n陷阱的个数及位置。求出玛丽从位置 1 开始有多少种跳跃方法能到达胜利的彼岸到达位置 n。
输入描述 第一行为两个整数 n,m 第二行为 m 个整数表示陷阱的位置
数据规模和约定 40 n 3, m 1 n m; 陷阱不会位于 1 及 n 上
输出描述 一个整数。表示玛丽跳到 n 的方案数
样例输入
4 1
2样例输出 1 解题思路 确定 dp 数组及其下标的含义 dp[i] 表示到达位置 i 的跳跃方法数。
确定递推公式 当满足index.count(i) 0 即此处没有陷阱 dp[i] dp[i-j] dp[i]
初始化 dp 数组 初始化为 0 即可。
确定遍历顺序 顺序遍历即可。 参考代码
n, m map(int, input().split())
index list(map(int, input().split()))
# dp[i] 表示到达位置 i 的跳跃方法数
# dp[0] 0 便于后续处理
dp [0 for i in range(n1)]
dp[1] 1
for i in range(2, n1):for j in [1, 2]:# 判断前两个位置是否有陷阱if index.count(i) 0:dp[i] dp[i-j] dp[i]
print(dp[-1])2^k进制数
题目 时间限制 1s
内存限制 128MB
题目描述 设 rrr 是个 2k2^k2k 进制数并满足以下条件
rrr 至少是个 222 位的 2k2^k2k 进制数。作为 2k2^k2k 进制数除最后一位外rrr 的每一位严格小于它右边相邻的那一位。将 rrr 转换为 222 进制数 qqq 后则 qqq 的总位数不超过 www。
在这里正整数 k(1≤k≤9)k(1≤k≤9)k(1≤k≤9)和 w(kw≤30000)w(kw≤30000)w(kw≤30000) 是事先给定的。
问满足上述条件的不同的 rrr 共有多少个 我们再从另一角度作些解释设 SSS 是长度为 www 的 01字符串即字符串 SSS 由 www 个0或1组成SSS 对应于上述条件中的 qqq。将 SSS 从右起划分为若干个长度为 kkk 的段每段对应一位2k2^k2k 进制的数如果 SSS 至少可分成 222 段则 SSS 所对应的二进制数又可以转换为上述的 2k2^k2k 进制数 rrr。
例设 k3w7k3w7k3w7。则 rrr 是个八进制数 (238)(2^38)(238)。由于 w7w7w7长度为 7 的 01 字符串按 3位一段分可分为 3 段即133左边第一段只有一个二进制位则满足条件的八进制数有
2位数 高位为16 个即 121314151617 高位为 25 个…高位为61个即67 。共 65…121 个。
3位数 高位只能是1第 2 位为 2 5 个即123124125126127第2位为34个…第 2 位为 61个即 167。共54…115个。 所以满足要求的 rrr 共有 36个。
输入描述 只有1行为两个正整数用一个空格隔开 kkk www
输出描述 1行是一个正整数为所求的计算结果即满足条件的不同的 rrr 的个数用十进制数表示要求最高位不得为0各数字之间不得插入数字以外的其他字符例如空格、换行符、逗号等。 提示作为结果的正整数可能很大但不会超过200位
样例输入 3 7 样例输出 36 解题思路 确定 dp 数组及其下标的含义 dp[i][j] 表示有 (i1) 位数字最高位数字是 j 时满足条件的数字个数。
确定递推公式 若 j0 dp[i][j] dp[i-1][j1]dp[i-1][j2]dp[i-1][j3]······ 也就是说最高位不是0的时候满足条件的数字个数是第二高位的数字大于最高位的数字的情况的和。 若j0dp[i][j] dp[i-1][j]dp[i-1][j1]dp[i-1][j2]dp[i-1][j3]······ 如果最高位是 0那么第二高位数字则可以取0。也就比上一个情况多加了个 dp[i-1][j]。
初始化 dp 数组 dp[0][j]1 即只有一位数字时只有一种情况
确定遍历顺序 顺序遍历即可。 此外注意最终结果的计算和处理具体见代码。 参考代码
import math
k, w map(int, input().split())
# rows, cols 为dp数组的行数和列数
rows, cols w//k1, 2**k
# i 是 2^k 进制下数字的位数
# j 是 每一位上可以取到的值
# dp[i][j] 表示有 (i1) 位数字最高位数字是 j 时满足条件的数字个数
dp [[0 for j in range(cols)] for i in range(rows)]
# 初始化 res为结果
res 0# dp 数组初始化
# dp[0][j] 表示有 1 位数字的情况
for j in range(cols):dp[0][j] 1# 递推
for i in range(1, rows):for j in range(cols):dp[i][j] sum(dp[i-1][j1:])if j 0:dp[i][j] dp[i-1][j]# 计算最后的结果
if w%k 0:# 此时最高位可以取 0 到 cols, 即最后一行所有情况都可以用res sum(dp[-1])
else:# 此时最高位只能取 0 到 2**(w%k)-1res sum(dp[-1][:2**(w%k)])# 题目中要求位数 2
# 需要减去只有一位数的情况
if w/k 1:res 0
else:res - 2**k
print(res)
