题解 | 最大能量和

import sys

data = sys.stdin.read().strip().split()
it = iter(data)
H = int(next(it))
W = int(next(it))
K = int(next(it))

# I, E, P分别为图像矩阵、能量矩阵和策略矩阵
I = [[0] * W for _ in range(H)]
E = [[0] * W for _ in range(H)]
P = [[0] * K for _ in range(K)]

# 读取图像矩阵和策略矩阵
for i in range(H):
    for j in range(W):
        I[i][j] = float(next(it))

for u in range(K):
    for v in range(K):
        P[u][v] = float(next(it))

# 计算能量矩阵
for i in range(H):
    for j in range(W):
        r = K // 2
        for u in range(K):
            for v in range(K):
                row = i + u - r
                col = j + v - r
                if 0 <= row < H and 0 <= col < W:
                    E[i][j] += I[row][col] * P[u][v]

# 定义每一列的最优状态
dp = [0] * H

for j in range(W):
    if j == 0:
        for i in range(H):
            dp[i] = E[i][j]
    else:
        maximum = 0
		# 每个位置的最大能量和有三种情况，与左上角最优值相加，与左侧最优值相加，与左下角最优值相加
        for i in range(H):
            if i - 1 >= 0:
                maximum = max(maximum, dp[i - 1] + E[i][j])
            maximum = max(maximum, dp[i] + E[i][j])
            if i + 1 < H:
                maximum = max(maximum, dp[i + 1] + E[i][j])
        dp[i] = maximum

ans = max(dp)
print(f"{ans:.1f}")