网站开发需要什么专业,市辖区郑州网站建设,官网开发建设公司地址电话,公选课网页制作与网站建设今日复习内容#xff1a;做题
例题1#xff1a;蓝桥骑士
问题描述#xff1a;
小蓝是蓝桥王国的骑士#xff0c;他喜欢不断突破自我。
这天蓝桥国王给他安排了N个对手#xff0c;他们的战力值分别为a1,a2,...,an#xff0c;且按顺序阻挡在小蓝的前方。对于这些对手小…今日复习内容做题
例题1蓝桥骑士
问题描述
小蓝是蓝桥王国的骑士他喜欢不断突破自我。
这天蓝桥国王给他安排了N个对手他们的战力值分别为a1,a2,...,an且按顺序阻挡在小蓝的前方。对于这些对手小蓝可以选择挑战也可以选择避战。
身为高傲的骑士小蓝从不走回头路且只愿意挑战战力值越来越高的对手。
请你算算小蓝最多会挑战多少名对手
输入描述
输入第一行包括一个整数N表示对手的个数
第二行包括N个整数a1,a2,...an表示每个骑士的战力值
1 N 3*10^51 ai 10^9。
输出描述
输出一行整数表示答案。
参考答案
import bisect
n int(input())
a list(map(int,input().split()))
q [a[0]]
for i in range(1,n):ind bisect.bisect_left(q,a[i])if ind len(q):q.append(a[i])else:q[ind] a[i]
print(len(q))
运行结果 以下是我对此题的理解
首先从输入中获取对手的个数和每个对手的战力值
创建一个空列表q用于存储已经被挑战过的对手的战力值
从第一个对手开始遍历到最后一个对手依次进行以下操作
使用二分查找在列表q中找到小于等于当前对手战力值的最大值的索引
如果找到的索引等于q的长度说明当前对手的战力值大于当前已经挑战过的所有对手的战力值将当前对手的战力值加入q中否则说明当前对手的战力值可以替换q中某个已经挑战过的对手的战力值最后输出q的长度就可以了。 例题2最长公共子序列
问题描述
给定一个长度为N的数组a和一个长度为M的数组b请你求出它们的最长公共子序列。
输入描述
输入第一行包括两个整数N和M分别表示数组a的长度和数组b的长度。
第二行输入包含N个整数a1,a2,...,an
第三行包含M个整数b1,b2,...bm
1 N,M 10^3,1 ai,bi 10^9
输出描述
输出一行整数表示答案
参考答案
a,b map(int,input().split())
A [0] list(map(int,input().split()))
B [0] list(map(int,input().split()))
f [[0]*(b 1)for i in range(a 1)]
for i in range(1,a 1):for j in range(1,b 1):if A[i] B[j]:f[i][j] f[i-1][j-1] 1else:f[i][j] max(f[i-1][j],f[i][j-1])print(f[a][b])
运行结果 这道题用的是动态规划比较简单我就不做过多解释了。 例题3倒水
问题描述
小秋家里来了n位客人编号为12...n现在小秋要给每个客人倒水。
每个客人都有一个满意度对于第i个客人满意度是这样定义的
如果小秋给第i个客人倒了ai毫升水客人的满意度为bi如果小秋给第i个客人倒了ci(ci ai)毫升水客人的满意度为di
如果小秋给第i为客人倒的水不足ai毫升也可以为0客人的满意度为ei。
现在小秋有m毫升水请问他要怎么倒水才能让所有客人的满意度之和最大呢你只需要求出所有客人的满意度之和的最大值。
输入描述
第一行输入两个正整数n和m表示客人的数量和小秋所拥有的水的体积
接下来n行每行5个整数ai,bi,ci,di,ei第i行表示给第i位客人倒了ai毫升水的满意度为bi给第i位客人倒了ci毫升水的满意度为di倒水不足ai毫升水的满意度为ei。
输出格式
输出仅一行包含一个整数表示所有课满意度之和的最大值。
参考答案
import os
import sys
n,m map(int,input().split())
f [[0]*(m 1) for i in range(n 1)]
for i in range(1,n 1):a,b,c,d,e map(int,input().split())for j in range(m 1):f[i][j] f[i - 1][j] eif j a:f[i][j] max(f[i][j],f[i - 1][j - a] b)if j c:f[i][j] max(f[i][j],f[i - 1][j - c] d)
print(f[n][m])
运行结果 以下是我对此题的理解
我就不写成文字了我把注释过的代码粘贴过来
import os
import sys# 输入客人数量n和水的体积m
n, m map(int, input().split())# 初始化动态规划数组ff[i][j]表示考虑前i个客人倒水体积为j时的最大满意度之和
f [[0] * (m 1) for i in range(n 1)]# 遍历每位客人
for i in range(1, n 1):# 获取当前客人的倒水参数a, b, c, d, e map(int, input().split())# 遍历可能的倒水体积for j in range(m 1):# 初始化当前状态为上一个状态加上当前客人倒水不足ai毫升时的满意度eif[i][j] f[i - 1][j] e# 如果当前剩余水量j大于等于ai即可以倒ai毫升水给当前客人if j a:# 尝试用当前水量j减去ai毫升水然后加上当前客人倒水ai毫升时的满意度bi与之前状态f[i-1][j-ai]相比较取最大值f[i][j] max(f[i][j], f[i - 1][j - a] b)# 如果当前剩余水量j大于等于ci即可以倒ci毫升水给当前客人if j c:# 尝试用当前水量j减去ci毫升水然后加上当前客人倒水ci毫升时的满意度di与之前状态f[i-1][j-ci]相比较取最大值f[i][j] max(f[i][j], f[i - 1][j - c] d)# 输出考虑了所有客人和水量为m时的最大满意度之和
print(f[n][m])例题4:盗墓分赃2
问题描述
在一个探险者的团队中小明和小红是合伙的盗墓贼。
他们成功盗取了一座古墓中的宝藏其中包括n件不同重量的宝贵文物和黄金第i件宝藏的重量为ai。
现在他们希望公平地分配这些宝藏使得小明所分得的宝藏的总重量等于小红所分得的宝藏的总重量。
请检查是否存在这样的分配方案需要注意的是不能对宝藏进行切割来平分重量只能整个宝藏进行分配。
输入格式
第一行包含一个正整数n表示有n件宝藏
接下来n行第i行表示第i件宝藏的重量ai。
输出格式
如果能公平分配就输出yes否则输出no。
参考答案
def work():n int(input())aa [0] [int(input())for i in range(n)]tot sum(aa)if tot % 2 ! 0:print(no)returntot // 2f [[False]*(tot 1) for i in range(n 1)]f[0][0] Truefor i in range(1,n 1):for j in range(tot 1):f[i][j] f[i - 1][j]if j aa[i]:f[i][j] f[i - 1][j - aa[i]]print(yes)if f[n][tot] else print(no)
if __name__ __main__:work()
运行结果 第一种做法有一个样例显示超时了所以我优化了一下。
第二种做法
def work():n int(input())aa [0] [int(input())for i in range(n)]tot sum(aa)if tot % 2 ! 0:print(no)returntot // 2f [False]*(tot 1)f[0] Truefor i in range(1,n 1):for j in range(tot,aa[i] - 1,-1):f[j] f[j - aa[i]]print(yes)if f[tot] else print(no)
if __name__ __main__:work()
以下是我对此题的理解
我用代码注释来表达我的思想
def work():# 输入宝藏的数量nn int(input())# 获取每件宝藏的重量并存储在列表aa中aa [0] [int(input()) for i in range(n)]# 计算所有宝藏的总重量tot sum(aa)# 如果总重量为奇数则无法公平分配输出no并返回if tot % 2 ! 0:print(no)return# 将总重量除以2得到每个人应分得的宝藏的总重量tot // 2# 创建一个布尔型数组ff[i]表示是否存在一种方案使得宝藏的总重量为if [False] * (tot 1)# 初始化f[0]为True表示当没有宝藏时总重量为0f[0] True# 遍历每件宝藏for i in range(1, n 1):# 从总重量到当前宝藏重量之间的位置开始遍历for j in range(tot, aa[i] - 1, -1):# 如果存在一种分配方案使得总重量为j的话那么也一定存在一种分配方案使得总重量为j 宝藏重量f[j] f[j - aa[i]]# 判断是否存在一种分配方案使得总重量为tot如果存在则输出yes否则输出noprint(yes) if f[tot] else print(no)if __name__ __main__:work()OK今天状态不错这几个题还好下一篇继续
