题解 | #最大能量和#

题目链接

最大能量和

题目描述

本问题分为两个步骤：

计算能量图：给定一个 $H \times W$ 的灰度图 $I$ 和一个 $K \times K$ 的策略矩阵 $P$ （ $K$ 为奇数），通过一个带零填充的卷积操作计算出能量图 $E$ 。
寻找最大路径：在能量图 $E$ 中，寻找一条从第 1 列到第 $W$ 列的路径，使得路径上的能量之和最大。路径的移动规则为：从 $(i, j)$ 只能移动到 $(i-1, j+1)$ , $(i, j+1)$ , 或 $(i+1, j+1)$ （右上、右、右下）。

输出这个最大的能量和，结果保留一位小数。

解题思路

这是一个复合问题，我们可以将其拆解为两个独立的子问题来解决。

第一步：计算能量图 $E$ (卷积操作)

核心公式：题目给出的能量计算公式 E[i][j] = Σ P[u][v] · I[i+u−r][j+v−r] 是一个标准的 2D 卷积。其中 r = K/2 (整数除法) 是卷积核的中心点半径。
边界处理：规则明确指出“若...越界，则视为该项贡献为0”，这是一种零填充 (Zero Padding) 的卷积方式。当卷积核覆盖到图像 $I$ 之外的区域时，我们将那些区域的像素值视为0。
实现：
1. 创建一个 $H \times W$ 的浮点数矩阵 E 并初始化为 0。
2. 使用四层嵌套循环：
  - 外两层遍历能量图 E 的每个坐标 $(i, j)$ 。
  - 内两层遍历策略矩阵 P 的每个坐标 $(u, v)$ 。
3. 在循环体内，计算出 P[u][v] 对应的图像 $I$ 的坐标 img_i = i + u - r 和 img_j = j + v - r。
4. 检查 (img_i, img_j) 是否在图像 $I$ 的边界内。如果是，则将 P[u][v] * I[img_i][img_j] 累加到 E[i][j]。

第二步：动态规划寻找最大能量路径

问题模型：这是一个在网格中寻找最大权重路径的经典动态规划问题。
状态定义：我们定义一个二维 DP 数组 dp[i][j]，其含义是：所有从第 1 列出发、并严格遵循移动规则、最终到达能量图位置 $(i, j)$ 的所有路径中，能获得的最大能量总和。
状态转移方程：
- 我们按列从左到右（ $j$ 从 1 到 $W-1$ ）来填充 dp 数组。
- 要计算 dp[i][j]，我们需要考虑能够到达 $(i, j)$ 的前一列 $(j-1)$ 的所有可能位置。根据移动规则，这些位置是：
  1. 左上: $(i-1, j-1)$
  2. 正左: $(i, j-1)$
  3. 左下: $(i+1, j-1)$
- dp[i][j] 的值等于当前位置 $(i, j)$ 的能量 E[i][j]，加上从这三个可能的前驱位置的 dp 值中取出的最大值。
- dp[i][j] = E[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])
- 在处理图像边界（第 0 行和第 $H-1$ 行）时，需要特别处理，只从有效的邻居位置进行转移。
基本情况 (Base Case)：
- 路径可以从第 1 列（索引为 0）的任意行开始。因此，dp 数组的第 0 列可以直接用能量图 E 的第 0 列来初始化：dp[i][0] = E[i][0]。
最终答案：
- 最优路径可以结束在最后一列（索引为 $W-1$ ）的任意行。因此，最终的答案就是 dp 数组最后一列中的最大值。
- max_energy_sum = max(dp[0][W-1], dp[1][W-1], ..., dp[H-1][W-1])
空间优化：由于计算第 j 列的 dp 值只依赖于第 j-1 列，我们可以使用两个一维数组（或一个二维 $H \times 2$ 的数组）进行滚动优化，将空间复杂度从 $\mathcal{O}(H \cdot W)$ 降至 $\mathcal{O}(H)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int h, w, k;
    cin >> h >> w >> k;

    vector<vector<double>> img(h, vector<double>(w));
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> img[i][j];
        }
    }

    vector<vector<double>> policy(k, vector<double>(k));
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < k; ++j) {
            cin >> policy[i][j];
        }
    }

    // 1. 计算能量图 E
    vector<vector<double>> energy(h, vector<double>(w, 0.0));
    int r = k / 2;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            for (int u = 0; u < k; ++u) {
                for (int v = 0; v < k; ++v) {
                    int img_i = i + u - r;
                    int img_j = j + v - r;
                    if (img_i >= 0 && img_i < h && img_j >= 0 && img_j < w) {
                        energy[i][j] += policy[u][v] * img[img_i][img_j];
                    }
                }
            }
        }
    }

    // 2. 动态规划寻找最大能量路径
    vector<vector<double>> dp = energy;

    for (int j = 1; j < w; ++j) {
        for (int i = 0; i < h; ++i) {
            double prev_max = dp[i][j-1];
            if (i > 0) {
                prev_max = max(prev_max, dp[i-1][j-1]);
            }
            if (i < h - 1) {
                prev_max = max(prev_max, dp[i+1][j-1]);
            }
            dp[i][j] += prev_max;
        }
    }

    // 3. 找到最后一列的最大值
    double max_energy_sum = 0.0;
    if (w > 0) {
        max_energy_sum = dp[0][w-1];
        for (int i = 1; i < h; ++i) {
            max_energy_sum = max(max_energy_sum, dp[i][w-1]);
        }
    }
    
    cout << fixed << setprecision(1) << max_energy_sum << "\n";

    return 0;
}

import java.util.Scanner;
import java.util.Locale;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in).useLocale(Locale.US);

        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();

        double[][] img = new double[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                img[i][j] = sc.nextDouble();
            }
        }

        double[][] policy = new double[k][k];
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                policy[i][j] = sc.nextDouble();
            }
        }

        // 1. 计算能量图 E
        double[][] energy = new double[h][w];
        int r = k / 2;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                for (int u = 0; u < k; u++) {
                    for (int v = 0; v < k; v++) {
                        int imgI = i + u - r;
                        int imgJ = j + v - r;
                        if (imgI >= 0 && imgI < h && imgJ >= 0 && imgJ < w) {
                            energy[i][j] += policy[u][v] * img[imgI][imgJ];
                        }
                    }
                }
            }
        }

        // 2. 动态规划寻找最大能量路径
        double[][] dp = new double[h][w];
        for (int i = 0; i < h; i++) {
            dp[i][0] = energy[i][0];
        }

        for (int j = 1; j < w; j++) {
            for (int i = 0; i < h; i++) {
                double prevMax = dp[i][j - 1];
                if (i > 0) {
                    prevMax = Math.max(prevMax, dp[i - 1][j - 1]);
                }
                if (i < h - 1) {
                    prevMax = Math.max(prevMax, dp[i + 1][j - 1]);
                }
                dp[i][j] = energy[i][j] + prevMax;
            }
        }

        // 3. 找到最后一列的最大值
        double maxEnergySum = 0.0;
        if (w > 0) {
            maxEnergySum = dp[0][w - 1];
            for (int i = 1; i < h; i++) {
                maxEnergySum = Math.max(maxEnergySum, dp[i][w - 1]);
            }
        }

        System.out.printf(Locale.US, "%.1f\n", maxEnergySum);
    }
}

import sys

def main():
    h, w, k = map(int, sys.stdin.readline().split())
    
    img = [list(map(float, sys.stdin.readline().split())) for _ in range(h)]
    policy = [list(map(float, sys.stdin.readline().split())) for _ in range(k)]

    # 1. 计算能量图 E
    energy = [[0.0] * w for _ in range(h)]
    r = k // 2
    for i in range(h):
        for j in range(w):
            current_energy = 0.0
            for u in range(k):
                for v in range(k):
                    img_i, img_j = i + u - r, j + v - r
                    if 0 <= img_i < h and 0 <= img_j < w:
                        current_energy += policy[u][v] * img[img_i][img_j]
            energy[i][j] = current_energy
    
    # 2. 动态规划寻找最大能量路径
    dp = [row[:] for row in energy] # 复制能量图作为dp初始状态

    for j in range(1, w):
        for i in range(h):
            prev_max = dp[i][j-1]
            if i > 0:
                prev_max = max(prev_max, dp[i-1][j-1])
            if i < h - 1:
                prev_max = max(prev_max, dp[i+1][j-1])
            dp[i][j] += prev_max
    
    # 3. 找到最后一列的最大值
    max_energy_sum = 0.0
    if w > 0:
        max_energy_sum = max(dp[i][w-1] for i in range(h))

    print(f"{max_energy_sum:.1f}")

if __name__ == "__main__":
    main()

算法及复杂度

算法: 卷积, 动态规划
时间复杂度: $\mathcal{O}(H \cdot W \cdot K^2)$ 。
- 计算能量图的卷积操作是主要的时间瓶颈，需要 $\mathcal{O}(H \cdot W \cdot K^2)$ 。
- 动态规划部分需要遍历能量图一次，时间复杂度为 $\mathcal{O}(H \cdot W)$ 。
- 总时间复杂度由卷积部分主导。
空间复杂度: $\mathcal{O}(H \cdot W)$ ，用于存储能量图 $E$ 和动态规划表 $dp$ 。

题解 | #最大能量和#

题目链接

题目描述

解题思路

第一步：计算能量图 (卷积操作)

第二步：动态规划寻找最大能量路径

代码

算法及复杂度

第一步：计算能量图 $E$ (卷积操作)