最大能量和

题意

给一张 $H \times W$ 的灰度图像 $I$ 和一个 $K \times K$ 的策略矩阵 $P$ （ $K$ 为奇数），先通过卷积（零填充）算出能量图 $E$ ：

$ $E[i][j] = \sum_{u=0}^{K-1}\sum_{v=0}^{K-1} P[u][v] \cdot I[i+u-r][j+v-r], \quad r = \lfloor K/2 \rfloor$ $

越界位置视为 0。然后从第 1 列任意一行出发，每步可以向右、右上、右下移动一格（不能越界），走到第 $W$ 列，求路径上能量值之和的最大值，保留 1 位小数。

思路

这道题分两步走，每步都很经典。

第一步：算能量图

就是一个标准的二维卷积。对每个位置 $(i,j)$ ，把 $K \times K$ 的核 $P$ 盖上去，逐元素乘再求和。越界的地方补零，也就是跳过不加。这步没什么花样，老老实实两层循环套两层循环就行。

第二步：路径 DP

能量图算完之后，问题就变成了：在一个 $H \times W$ 的网格上，从第 0 列任意行出发，每步向右走一格（可以保持同行、上移一行、下移一行），到达第 $W-1$ 列，求经过格子的最大权值和。

这是一个非常经典的 DP。定义 $dp[i]$ 为「当前列第 $i$ 行的最大能量和」，初始时 $dp[i] = E[i][0]$ 。然后逐列转移：

$ $dp'[i] = E[i][j] + \max(dp[i-1],\; dp[i],\; dp[i+1])$ $

注意边界： $i=0$ 时没有 $dp[i-1]$ ， $i=H-1$ 时没有 $dp[i+1]$ 。最后答案就是最后一列 $dp$ 数组的最大值。

你可能会问：为什么不用二维 $dp[i][j]$ ？当然可以，但既然每列只依赖前一列，用滚动数组压成一维就够了，省空间也更简洁。

复杂度

时间： $O(H \cdot W \cdot K^2 + H \cdot W)$ ，卷积是大头
空间： $O(H \cdot W)$ 存能量图

代码

Python3
C++

import sys

def main():
    data = sys.stdin.read().split()
    idx = 0
    H = int(data[idx]); idx += 1
    W = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1

    I = []
    for i in range(H):
        row = []
        for j in range(W):
            row.append(float(data[idx])); idx += 1
        I.append(row)

    P = []
    for i in range(K):
        row = []
        for j in range(K):
            row.append(float(data[idx])); idx += 1
        P.append(row)

    r = K // 2

    # 计算能量图
    E = [[0.0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            s = 0.0
            for u in range(K):
                for v in range(K):
                    ii = i + u - r
                    jj = j + v - r
                    if 0 <= ii < H and 0 <= jj < W:
                        s += P[u][v] * I[ii][jj]
            E[i][j] = s

    # 路径 DP
    dp = [E[i][0] for i in range(H)]
    for j in range(1, W):
        new_dp = [0.0] * H
        for i in range(H):
            best = dp[i]
            if i > 0:
                best = max(best, dp[i - 1])
            if i < H - 1:
                best = max(best, dp[i + 1])
            new_dp[i] = best + E[i][j]
        dp = new_dp

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

main()

#include <bits/stdc++.h>
using namespace std;

int main(){
    int H, W, K;
    scanf("%d%d%d", &H, &W, &K);

    vector<vector<double>> I(H, vector<double>(W));
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            scanf("%lf", &I[i][j]);

    vector<vector<double>> P(K, vector<double>(K));
    for(int i = 0; i < K; i++)
        for(int j = 0; j < K; j++)
            scanf("%lf", &P[i][j]);

    int r = K / 2;

    vector<vector<double>> E(H, vector<double>(W, 0.0));
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++){
            double s = 0;
            for(int u = 0; u < K; u++)
                for(int v = 0; v < K; v++){
                    int ii = i + u - r, jj = j + v - r;
                    if(ii >= 0 && ii < H && jj >= 0 && jj < W)
                        s += P[u][v] * I[ii][jj];
                }
            E[i][j] = s;
        }

    vector<double> dp(H);
    for(int i = 0; i < H; i++) dp[i] = E[i][0];

    for(int j = 1; j < W; j++){
        vector<double> ndp(H);
        for(int i = 0; i < H; i++){
            double best = dp[i];
            if(i > 0) best = max(best, dp[i-1]);
            if(i < H-1) best = max(best, dp[i+1]);
            ndp[i] = best + E[i][j];
        }
        dp = ndp;
    }

    printf("%.1f\n", *max_element(dp.begin(), dp.end()));
    return 0;
}