一篇简单的做题记录

从模板题找了几个做的最多的题

1. 排序

题目链接：1.排序 - 蓝桥云课

1
2
3
input();a=sorted(list(map(int,input().split())))
print(*a) #直接将列表的元素以空格分隔打印
print(*a[::-1]) #排序后的倒序就是逆序

2. 走迷宫

题目链接：2.走迷宫 - 蓝桥云课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# n,m=map(int,input().split())
# g=[list(map(int,input().split())) for i in range(n)]
# flag=[[1]*m for _ in range(n)]
# x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
# class Node:
#     def __init__(self,x,y,val,cnt):
#         self.x=x
#         self.y=y
#         self.val=val
#         self.cnt=cnt
# q=[Node(x1,y1,g[x1][y1],0)]
# ans=0xfffffffff
# # print(ans)
# while q:
#     node=q[0]
#     # print(node.x,node.y)
#     del q[0]
#     # q.pop(0)
#     if node.x==x2 and node.y==y2:
#         ans=min(node.cnt,ans)
#     for a,b in [[0,1],[0,-1],[-1,0],[1,0]]: #右左下上
#         if 0<=node.y+b<m and 0<=node.x+a<n and g[node.x+a][node.y+b] and flag[node.x+a][node.y+b]:
#             q.append(Node(node.x+a,node.y+b,g[node.x+a][node.y+b],node.cnt+1))
#             flag[node.x+a][node.y+b]=0
# print(-1 if ans==0xfffffffff else ans)

# 看了题解后改进自己的
n, m = map(int, input().split())
g = [list(map(int, input().split())) for i in range(n)]
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
q = [[x1, y1, 0]]
while q:
    x, y, cnt = q.pop(0)
    if x == x2 and y == y2:
        print(cnt)
        break
    for a, b in map(lambda i:(i[0] + x, i[1] + y),((0, 1), (0, -1), (-1, 0), (1, 0))):  # 右左下上
        if 0 <= a < n and 0 <= b < m and g[a][b]:
            q.append((a, b, cnt + 1))
            g[a][b] = 0
else:
    print(-1)
"""
结合地图进行dfs，一开始起点进队列，队列不为空时进行循环，每次循环，队列首出队列，然后往上下左右四个方向走，超过地图大小或是阻碍或走过了就不入队列，原本用的class用inf记录步数，后来看题解：
可以用三元组，一开始头节点的出队列可以直接用pop(0)接收，再分给三个变量记录，最后走到了终点直接输出break否则输出-1
当然，最妙的在于走过的直接赋值地图的值为0表示走过了，这样就不用再走了，也不用开标志数组了，与原来地图的阻碍同义
"""

3. 小明的背包1

题目链接：3.小明的背包1 - 蓝桥云课

知识来源的B站链接：

带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 自己看B站代码随想录后理解得到的代码
# n, c = map(int, input().split())
# dp = [[0] * (c + 1) for i in range(n)]  # 0~i个物品选取任意个物品背包容量为j所能达到最大价值
# for i in range(n):  # 0-n个物品
#     w, v = map(int, input().split())
#     if i == 0:  # 第一行初始化
#         for j in range(c + 1):
#             if j >= w:
#                 dp[i][j] = v
#     else:
#         for j in range(c + 1):  # 不同背包容量
#             if j >= w:  # 容量更大才能放
#                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)  # 不放价值更多还是放（背包容量减少w，价值+v）价值更多
#             else:
#                 dp[i][j] = dp[i - 1][j]
# print(dp[n - 1][c])

# 1.看题解的改进，如果多开一行就不怕数组越界了，从而不用第一行的初始化，直接进行判断
# 2.背包够不够放这个物品的判断可以写道背包容量的循环范围里--->错错错！！！！ 那是一维滚动数组，二维不可用
# n, c = map(int, input().split()) #物品个数和背包容量
# dp = [[0] * (c + 1) for i in range(n+1)]  # 1~i（最大为n）个物品选取任意个物品背包容量为j(最大为c)所能达到最大价值
# for i in range(1,n+1):  # 1~n个物品
#     w, v = map(int, input().split()) #这个物品的
#     for j in range(c + 1):  # 不同背包容量下物品的选择
#         if j>=w: #物品放得下
#             dp[i][j] =  max(dp[i - 1][j],dp[i - 1][j - w] + v)  # 这个物品不放（背包容量不变，物品还是前i-1个物品）价值更多还是放（背包容量减少w，价值+v）价值更多
#         else:
#             dp[i][j]=dp[i-1][j] #物品放不下，还是这个物品不放时的价值
# print(dp[n][c])

# print(list(range(2,5,-1)))
# 一维滚动dp：利用把本层的数组作为上一层来看待压缩，左上角->左边的值（二维->一维）保证每个物品只取一次，只有逆序才保证左上角的值不会改变
n, c = map(int, input().split())  # 物品个数和背包容量
dp = [0] * (c + 1)  # 1~i（最大为n）个物品选取任意个物品背包容量为j(最大为c)所能达到最大价值
for i in range(1, n + 1):  # 1~n个物品
    w, v = map(int, input().split())  # 这个物品的
    for j in range(c, w - 1, -1):  # 不同背包容量下物品的选择
        dp[j] = max(dp[j], dp[j - w] + v)  # 这个物品不放（背包容量不变，物品还是前i-1个物品）价值更多还是放（背包容量减少w，价值+v）价值更多
print(dp[c])