今日复习内容：做题
例题1：蓝桥骑士
问题描述：
小蓝是蓝桥王国的骑士，他喜欢不断突破自我。
这天蓝桥国王给他安排了N个对手，他们的战力值分别为a1,a2,...,an，且按顺序阻挡在小蓝的前方。对于这些对手小蓝可以选择挑战，也可以选择避战。
身为高傲的骑士，小蓝从不走回头路，且只愿意挑战战力值越来越高的对手。
请你算算小蓝最多会挑战多少名对手？
输入描述：
输入第一行包括一个整数N，表示对手的个数；
第二行包括N个整数：a1,a2,...an，表示每个骑士的战力值；
1 <= N <= 3*10^5，1 <= 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] + 1
else:
f[i][j] = max(f[i-1][j],f[i][j-1])
print(f[a][b])运行结果：
这道题用的是动态规划，比较简单，我就不做过多解释了。
例题3：倒水
问题描述：
小秋家里来了n位客人，编号为1，2，...，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] + e
if 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())
# 初始化动态规划数组f，f[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毫升时的满意度ei
f[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')
return
tot //= 2
f = [[False]*(tot + 1) for i in range(n + 1)]
f[0][0] = True
for 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')
return
tot //= 2
f = [False]*(tot + 1)
f[0] = True
for 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():
# 输入宝藏的数量n
n = 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
# 创建一个布尔型数组f，f[i]表示是否存在一种方案使得宝藏的总重量为i
f = [False] * (tot + 1)
# 初始化f[0]为True，表示当没有宝藏时，总重量为0
f[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'，否则输出'no'
print('yes') if f[tot] else print('no')
if __name__ == '__main__':
work()
OK，今天状态不错，这几个题还好，下一篇继续！
