怎样网站建设,ps做网站时画布宽度,网站开发专业毕业设计,网站集约化建设讲话备战2024年蓝桥杯算法学习 -- 每日一题 Python大学A组 试题一#xff1a;摘花生 试题二#xff1a;最低通行费用 试题三#xff1a;方格取数 试题四#xff1a;传纸条 试题一#xff1a;摘花生
【题目描述】 Hello Kitty想摘点花生送给她喜…备战2024年蓝桥杯算法学习 -- 每日一题 Python大学A组 试题一摘花生 试题二最低通行费用 试题三方格取数 试题四传纸条 试题一摘花生
【题目描述】 Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)从西北角进去东南角出来。地里每个道路的交叉点上都有种着一株花生苗上面有若干颗花生经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。 【输入格式】 第一行是一个整数T代表一共有多少组数据。 接下来是T组数据。 每组数据的第一行是两个整数分别代表花生苗的行数R和列数 C。 每组数据的接下来R行数据从北向南依次描述每行花生苗的情况。每行数据有C个整数按从西向东的顺序描述了该行每株花生苗上的花生数目M。
【输出格式】 对每组输入数据输出一行内容为Hello Kitty能摘到得最多的花生颗数。
【数据范围】 1≤T≤100, 1≤R,C≤100, 0≤M≤1000
【输入样例】
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
【输出样例】
8
16
【解题思路】 线性DP中的数字三角形模型基础模型状态转移方程f[i][j] max(f[i-1][j] , f[i][j-1]) w[i][j]。
【Python程序代码】
T int(input())
for _ in range(T):r,c map(int,input().split())a [[0]*(c5)]for i in range(r):a.append([0]list(map(int,input().split())))f [[0]*(c5) for _ in range(r5)]for i in range(1,r1):for j in range(1,c1):f[i][j] max(f[i-1][j],f[i][j-1])a[i][j]print(f[r][c])试题二最低通行费用
【题目描述】 本题大意上给定一个 n×n的矩阵让我们从左上角出发最终走到右下角走过的方块数量的不能超过 2n−1个求所有路线中经过的方块的总价值最少的路线。
【解题思路】 和上一题相比改了一些条件比如增加了一个不能超过2n-1个方块考虑一下11到nn的曼哈顿距离发现d 2*n-2同时题目要求的是求总价值最小在2*n-2的最短路径上加上一个方块一定会大于等于这2*n-2个方块的价值所以本题可以套上面题目的板子。
【Python程序代码】
n int(input())
f [[1e9]*(n5) for _ in range(n5)]
a [[0]*(n5)]
for i in range(n):a.append([0]list(map(int,input().split())))
f[0][1]f[1][0]0
for i in range(1,n1):for j in range(1,n1):f[i][j] min(f[i][j-1],f[i-1][j])a[i][j]
print(f[n][n]) 试题三方格取数
【题目描述】 设有N×N 的方格图(N≤9)我们将其中的某些方格中填入正整数而其他的方格中则放入数字 0。如下图所示见样例: 某人从图的左上角的 A 点出发可以向下行走也可以向右走直到到达右下角的 B 点。在走过的路上他可以取走方格中的数取走后的方格中将变为数字 0。 此人从 A 点到 B 点共走两次试找出 2 条这样的路径使得取得的数之和为最大。
【输入数据】 输入的第一行为一个整数 N表示 N×N 的方格图接下来的每行有三个整数前两个表示位置第三个数为该位置上所放的数。一行单独的 0 表示输入结束。
【输出数据】 只需输出一个整数表示 2 条路径上取得的最大的和。
【输入样例】
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
【输出样例】
67
【解题思路】 需要考虑两条路径如何考虑更好呢如果说分别考虑的话如何判断是否重合呢且这两者相加也不一定是最大值所以如果能够同时考虑两条路就好了首先两条路的曼哈顿距离一定是相等的所以我们可以考虑枚举每一条路径走的行的数量列的数量可以用曼哈顿距离-列的数量所以f[k][i][j]表示曼哈顿距离为k且第一条路径走了i行k-i列第二条路径走了j行k-j列那么如何考虑状态转移呢每一个f[k][i][j]可以由第一条路径往右走或者往下走过来也即使f[k-1][i][j]和f[k-1][i-1][j]第二条路径也是往右或往下f[k-1][i][j]f[k-1][i][j-1]那也就是四种状态f[k-1][i-1][j-1]、f[k-1][i][j-1]、f[k-1][i-1][j]、f[k-1][i][j]。
【Python程序代码】
n int(input())
w [[0]*(n5) for _ in range(n5)]
a,b,c map(int,input().split())
while not (a0 and b0 and c0):w[a][b] ca, b, c map(int, input().split())
f [[[0]*(n5) for _ in range(n5)] for i in range(2*n5)]
for k in range(2,2*n1):for i in range(1,n1):for j in range(1,n1):if k-i0 or k-j0 or k-in or k-jn:continuev w[i][k-i]t f[k][i][j]if i!j:vw[j][k-j]t max(t, f[k-1][i-1][j-1])t max(t, f[k-1][i][j-1])t max(t, f[k-1][i-1][j])t max(t, f[k-1][i][j])f[k][i][j] tv
print(f[2*n][n][n])试题四传纸条
【题目描述】 小渊和小轩是好朋友也是同班同学他们在一起总有谈不完的话题。一次素质拓展活动中班上同学安排坐成一个 m 行 n 列的矩阵而小渊和小轩被安排在矩阵对角线的两端因此他们就无法直接交谈了。幸运的是他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里小渊坐在矩阵的左上角坐标 (1,1)小轩坐在矩阵的右下角坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中小渊希望给小轩传递一张纸条同时希望小轩给他回复。班里每个同学都可以帮他们传递但只会帮他们一次也就是说如果此人在小渊递给小轩纸条的时候帮忙那么在小轩递给小渊的时候就不会再帮忙反之亦然。 还有一件事情需要注意全班每个同学愿意帮忙的好感度有高有低注意小渊和小轩的好心程度没有定义输入时用 0 表示可以用一个 0∼100的自然数来表示数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条即找到来回两条传递路径使得这两条路径上同学的好心程度之和最大。现在请你帮助小渊和小轩找到这样的两条路径。
【输入格式】 第一行有 2 个用空格隔开的整数 m 和 n表示学生矩阵有 m 行 n 列。 接下来的 m 行是一个 m×n 的矩阵矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度每行的 n 个整数之间用空格隔开。
【输出格式】 输出一个整数表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。 【数据范围】 1≤n,m≤50
【输入样例】
3 3
0 3 9
2 8 5
5 7 0
【输出样例】
34
【解题思路】 和上面一题类似多了一个路径不可重复考虑一下用上面的方法做一下得到两条路径如果路径没有交叉和重叠点那么上面的就是答案。如果有交叉呢。 对于有交叉的我们可以通过移动变到没有交叉但是个别点重合。对于重复我们必然可以在两条路线中找到额外的一条或两条路线使得新的路线不发生重合。如下图 由于原路线是最优解则必然 wAwB0否则最优解路径必然是经过A或B的因此我们可以通过微调其中的一条路线使之不经过重合点 C同时路线的总价值没有减少。所以可以直接用方格取数的方法。
【Python程序代码】
n,m map(int,input().split())
a [[0]*(m5)]
for i in range(n):a.append([0]list(map(int,input().split())))
f [[[0]*(n5) for i in range(n5)] for j in range(nm5)]
for k in range(2,nm1):for i in range(1,n1):for j in range(1,n1):if k-im or k-i0 or k-jm or k-j0:continuet f[k][i][j]v a[i][k-i]if i!j:va[j][k-j]t max(t, f[k-1][i-1][j-1])t max(t, f[k-1][i-1][j])t max(t, f[k-1][i][j-1])t max(t, f[k-1][i][j])f[k][i][j] tv
print(f[nm][n][n])
