#P4274. 第2题-最大能量路径

print输出的方式# 想要保留一位小数就在 score 后面加 :.1f print(f姓名: {name}, 年龄: {age}, 最大能量: {score:.1f}) # 输出结果: # 姓名: 小明, 年龄: 24, 最大能量: 119.6 # 注意大括号里面的格式控制不需要写变量名只写 :.1f print(姓名: {}, 年龄: {}, 最大能量: {:.1f}.format(name, age, score)) # 输出结果同上 print(姓名: %s, 年龄: %d, 最大能量: %.1f % (name, age, score)) # 输出结果同上纯用python基础语法实现动态规划import sys import numpy as np def solve(): data sys.stdin.read().split() if not data: return H int(data[0]) W int(data[1]) K int(data[2]) figure [] matrix [] idx 4 for _ in range (H): row [] for _ in range(W): row.append(int(data[idx])) idx 1 figure.append(row) for _ in range(K): row [] for _ in range(K): row.append(int(data[idx])) idx 1 matrix.append(row) # print(figure:\n,figure) # print(matrix:\n, matrix) pad_size K//2 padded_H H pad_size*2 padded_W W pad_size*2 padded_figure [] for _ in range(padded_H): padded_figure.append([0]*padded_W) for i in range(H): for j in range(W): padded_figure[ipad_size][jpad_size] figure[i][j] energy [] for i in range(H): row [] for j in range(W): current_energy 0 for ki in range(K): for kj in range(K): img_val padded_figure[kii][kjj] weight matrix[ki][kj] current_energy img_val*weight row.append(current_energy) energy.append(row) #print(energy:\n,energy) INF float(-inf) dp [[INF]*W for _ in range(H)] # 初始化 for i in range(H): dp[i][0] energy[i][0] for j in range(1,W): for i in range(H): choices [] # 1. 纯向右走 (前一列的同一行) choices.append(dp[i][j-1]) if i0: choices.append(dp[i-1][j-1]) if iH-1: choices.append(dp[i1][j-1]) dp[i][j] energy[i][j]max(choices) max_energyINF for i in range(H): if dp[i][W-1]max_energy: max_energy dp[i][W-1] print(f{max_energy:.1f}) if __name__ __main__: solve()numpy实现import sys import numpy as np def solve(): data sys.stdin.read().split() if not data: return H int(data[0]) W int(data[1]) K int(data[2]) # 一键读取并变形 # data[4 : 4 H*W] 把图像的数字全切出来。 # np.array 会自动把字符串转成数字然后 .reshape(H, W) 瞬间把它揉成二维矩阵 figure np.array(data[4 : 4 H*W], dtypenp.float64).reshape(H, W) matrix np.array(data[4 H*W : 4 H*W K*K], dtypenp.float64).reshape(K, K) # 一键补零 pad_size K // 2 # np.pad 函数直接在矩阵外面围上一圈 0再也不用手动算坐标造画布了 padded_figure np.pad(figure, pad_widthpad_size, modeconstant, constant_values0) # 矩阵切片卷积 (消灭 ki, kj 循环) energy np.zeros((H, W), dtypenp.float64) for i in range(H): for j in range(W): # 直接像切蛋糕一样从大画布上切下一块 K x K 的窗口 window padded_figure[i : iK, j : jK] # 两个矩阵直接相乘对位相乘然后 np.sum 全部加起来一行代码搞定 energy[i, j] np.sum(window * matrix) # 向量化动态规划 (消灭 i 循环) INF float(inf) dp np.full((H, W), -INF, dtypenp.float64) # 初始化第一列 dp[:, 0] energy[:, 0] # 逐列向右推进 (DP 的列之间有依赖所以外层 j 循环必须保留) for j in range(1, W): # 把前一列的所有状态整条抽出来 prev_col dp[:, j-1] # 我们要造出 3 条可能的历史路径让它们正面刚 # 1. 从正左方来 (保持原样) left prev_col # 2. 从左上方来 (把整条前一列往下平移一格最顶上空出来的地方补 -INF) top_left np.pad(prev_col[:-1], (1, 0), constant_values-INF) # 3. 从左下方来 (把整条前一列往上平移一格最底下空出来的地方补 -INF) bottom_left np.pad(prev_col[1:], (0, 1), constant_values-INF) # 把这 3 种情况像汉堡一样叠起来 (vstack)然后竖着比较 (axis0)挑出每一行的最大值 max_choices np.max(np.vstack((left, top_left, bottom_left)), axis0) # 当前列 当前死工资 历史最大值 (一整列瞬间计算完毕) dp[:, j] energy[:, j] max_choices # 取最后一列的最大值 max_energy np.max(dp[:, W-1]) print(f{max_energy:.1f}) if __name__ __main__: solve()