python 基础知识点（蓝桥杯python科目个人复习计划59）

今日复习内容：做题

例题1：建造房屋

问题描述：

小蓝和小桥是两位年轻的建筑师，他们正在设计一座新的城市。

在这个城市中，有N条街道，每条街道上有M个位置可以建造房屋（一个位置只能建造一个房屋），建造一个房屋的费用是1元，小蓝和小桥共有k元的建造预算。

现在，他们想知道，一共有多少种建造方案，满足以下要求:

在每条街道上，至少建造一座房屋；

建造的总成本不能超过k元。

由于方案数可能很大，他们只需要输出答案对10^9 + 7取模的结果。

输入格式：

一行3个整数N，M(1 = N,M <= 30)和K(1 <= K <= N * M)，分别表示街道数，街道位置数和预算。

输出格式：

一个整数，表示满足条件的方案数对10^9 + 7取模的结果。

参考答案：

mod = int(1e9) + 7
n,m,k = map(int,input().split())
f = [[0] * (k + 1) for i in range(n + 1)]
for i in range(k + 1):
    f[0][i] = 1
for i in range(1,n + 1):
    for j in range(k + 1):
        for z in range(1,m + 1):
            if j >= z:
                f[i][j] = (f[i][j] + f[i - 1][j - z]) % mod
print(f[n][k])

运行结果：

以下是我对此题的理解：

这道题涉及动态规划，目标的计算在给定预算下，满足建造要求的方案数。

1.定义了一个二维数组f，其中f[i][j]表示在前i条街道上，总成本为j的方案数。

2.初始化数组f[0][i]，表示在0条街道上，总成本为i的方案数，初始化为1，因为无论预算多少，都有一种方案（不建造任何房屋）。

3.使用3层循环，其中第一层循环遍历街道，第二层循环遍历总成本，第3层循环遍历每个街道上可建造的位置。

4.在内层循环中，检查当前总成本j是否大于街道上可建造的位置数z。如果满足条件，则需要更新f[i][j]，加上之前街道i - 1上总成本为j - z的方案数。

5.最终输出结果为f[n][k]，表示在前n条街道上，总成本为k的方案数。

n,m,k = map(int,input().split())：从标准输入读取三个整数，分别表示街道数n，街道位置数m和预算k

f = [[0] * (k + 1) for i in range(n + 1):这一行代码创建了一个二维列表f，其中包含n + 1行，每行包含k + 1个元素，初始值都为0，这个列表用于存储动态规划过程中的中间结果。

for i in range(k + 1)：这个循环遍历了k + 1个预算值，用于初始化第0条街道上的方案数。

f[0][i] = 1：这一行将第0条街道上总成本为i的方案数记为1，因为无论预算多少，都要一个方案，不建造任何房屋。

for i in range(1,n + 1)：这个循环遍历了1到n条街道

for j in range(k + 1)：这个循环遍历了k + 1个总成本值，，用于计算每条街道上的方案数

for z in range(1,m + 1)：这个循环遍历了每个街道上可建造的位置数，从1到m

if j >= z：这个条件判断语句检查当前总成本j是否大于等于当前街道上可建造的位置数z

f[i][j] = (f[i][j] + f[i - 1][j - z]) % mod：这一行更新了当前街道上总成本为j的方案数。它将之前街道i - 1上总成本为j - z的方案数加到当前街道上，并对结果取模。

print(f[n][k])：最后输出结果，表示前n条街道上，总成本为k的方案数。

例题2：破损的楼梯

问题描述：

小蓝来到了一座高耸的楼梯前，楼梯共有N级台阶，从第0级台阶出发。小蓝可以迈上1或2级台阶。但是，楼梯上的第a1级，第a2级，第a3级，以此类推，共M级台阶的台阶面坏掉了，不能踩上去。

现在，小蓝想要到达楼梯的顶端，也就是第N级台阶，但他不能踩到坏了的台阶上，请问他有多少种不能踩到坏了的楼梯但是能到达第N级台阶的方案数？

由于方案数很大，请输出其对10^9 + 7的结果。

输入格式：

第一行包含两个正整数N(1 <= N <= 10^5)和M(0 <= M <= N)，表示台阶总数和坏了的台阶级数。

接下来来N行，包含N个整数a1,a2,...,aM,(1 <= a1 < a2 <... < aM <= N)，表示坏掉的台阶编号。

输出格式：

输出一个整数，表示小蓝到达楼梯顶层的方案数，对10^9 + 7取模。

参考答案：

mod = int(1e9) + 7
n,m = map(int,input().split())
mm = list(map(int,input().split()))
vis = [0] * (n + 1)
for i in mm:
    vis[i] = 1
f = [0] * (n + 1)
f[0] = 1
f[1] = 1 - vis[1]
for i in range(2,n + 1):
    if not vis[i]:
        f[i] = (f[i - 1] + f[i - 2]) % mod
print(f[n])

运行结果：

以下是我对此题的理解：

这个题是一个很经典的冬天规划问题，以下是我的思路：

n,m = map(int,input().split())：从标准输入中读取两个整数，分别表示台阶总数和坏了的台阶数。

mm = list(map(int,input().split()))：从输入中读取坏了的台阶的编号，并将它们储存在列表mm中

vis = [0] * (n + 1)：创建了一个长度为n + 1的列表，用于标记每个台阶是否坏掉。如果台阶i坏了，则vis[i]的值为1，否则为0.

for i in mm:vis[i] = 1：这个循环将坏掉的台阶编号所对应的vis列表中的值记为1，表示这些台阶坏了。

f = [0] * (n + 1)：用于存储动态规划过程中的中间结果，f[i]表示到达第i级台阶的方案数

f[0] = 1：初始第0级台阶的方案数为0，因为小蓝从第0级台阶出发。

f[1] = 1 - vis[1]：初始化第一级台阶的方案数，如果第一级台阶坏了，则方案数为0，否则为1.

for i in range(2,n + 1)：遍历剩下的台阶

if not vis[i]：用于判断此台阶是否坏了，如果没有，就继续执行下面的代码

f[i] = (f[i - 1] + f[i - 2]) % mod：这一行更新了到达第i级台阶的方案数，如果第i - 1级台阶坏了，只能通过第i - 2级台阶才能到达第i级台阶，这里需要考虑台阶的可行性。

print(f[n])：最终输出结果

例题3：拍照

问题描述：

小椒是个摄影爱好者。恰逢班级合照，他受邀帮忙拍照（站成一排）。这本是一件简单的事，但由于啾啾是个完美主义者，他希望拍的照片必须符合美学，即存在一个身高较大值，使得较大值无论往左还是往右身高都是递减的，数学上可以表示为：a[1] <= ... <= a[i] >= a[i + 1] >= ...>= a[n]。同学们已经站好了，但是不符合美学，你需要找出尽可能少的同学出列重新进行排列。请问最少需要出列几个同学？

输入格式：

第一行输入n，表示有n个同学，接下来的n行，输入校友身高，其中第i行输入a[i]( 1 <= i <= n)，输入编号为i的校友的身高（单位是毫米）。

(1 <= n <= 100,1500 <= a[i] <= 1900)

输出格式：

输出一个整数，表示最少需要出队多少个同学。

参考答案：

n = int(input())
a = list(map(int, input().split()))
dp1 = [0] * (n + 1)
dp2 = [0] * (n + 1)

for i in range(1, n + 1):
    dp1[i] = 1
    for j in range(1, i):
        if a[i - 1] >= a[j - 1]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

for i in range(n, 0, -1):
    dp2[i] = 1
    for j in range(n, i, -1):
        if a[i - 1] >= a[j - 1]:
            dp2[i] = max(dp2[i], dp2[j] + 1)

ans = 0
for i in range(1, n + 1):
    ans = max(ans, dp1[i] + dp2[i] - 1)

print(n - ans)

运行结果：