python 网站开发 sae,站酷设计师网站,深圳外贸网络推广,可信网站是否有规定必须做今日复习内容#xff1a;做题
例题1#xff1a;建造房屋
问题描述#xff1a;
小蓝和小桥是两位年轻的建筑师#xff0c;他们正在设计一座新的城市。
在这个城市中#xff0c;有N条街道#xff0c;每条街道上有M个位置可以建造房屋#xff08;一个位置只能建造一个房…今日复习内容做题
例题1建造房屋
问题描述
小蓝和小桥是两位年轻的建筑师他们正在设计一座新的城市。
在这个城市中有N条街道每条街道上有M个位置可以建造房屋一个位置只能建造一个房屋建造一个房屋的费用是1元小蓝和小桥共有k元的建造预算。
现在他们想知道一共有多少种建造方案满足以下要求:
在每条街道上至少建造一座房屋
建造的总成本不能超过k元。
由于方案数可能很大他们只需要输出答案对10^9 7取模的结果。
输入格式
一行3个整数NM(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] 1for 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] 1for 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)
运行结果 以下是我对此题的理解
n int(input())从标准输入读取同学的数量n
a list(map(int,input().split()))从标准输入读取每个同学的身高并将它们存储在列表a中
dp1和dp2分别代表从左到右和从右到左的动态规划数组。它们的长度都是n 1用于存储每个位置的最长符合美学要求的子序列长度。
对于dp1数组dp1[i]表示以同学i为结束的最长符合美学要求的子序列长度初始化所有值为1因为每个同学本身就是一个符合美学要求的子序列
对于dp2数组dp2[i]表示以同学i为开始的最长符合美学要求的子序列长度初始化所有值为1因为每个同学本身就是一个符合美学要求的子序列。
对于每个同学i在dp1中遍历所有在i之前的同学j之后就是比较再输出答案就可以了。 OK前几天写比赛论文去了没时间复习从今天开始必须挤时间了。
那这篇就这样了下一篇继续
