思路

预处理能量： 先按上式计算整张图的能量矩阵 $E$ ，复杂度 $O(H\cdot W\cdot K^2)$ 。
动态规划建模： 用 $f_{i,j}$ 表示走到位置 $(i,j)$ 的最大能量和：
- 边界： $f_{i,0}=E_{i,0}$ ，对所有 $i\in[0,H-1]$ 。
- 转移：

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

1000ms

Tried: 2980

Accepted: 704

Difficulty: 5

所属公司 : 华为

算法与标签>动态规划

题目内容

在自动驾驶系统中，车道线识别是核心功能之一。车道线通常具有连续性，从图像左侧到右侧逐渐展开。

为了识别出最可能的车道线路径，我们可以在图像中找到一条路径，使得路径上所有像素的信号值与策略矩阵的乘积之和最大。

现定义每个位置的能量值为策略矩阵与该位置周边信号值的乘积和。

给定一个 $H×W$ 的图像以及一个 $K×K$ 的策略矩阵，用于模拟不同方向的路径选择策略。

你需要从图像的第一列任意像素出发，走到最后一列任意像素，每一步只能向右、右上、右下移动一格。

在行进的过程中，需要实时的收集能量值，请找到一条路径，使得路径上的能量值之和最大。

输入描述

第一行输入 $H$ $W$ $K$ $K$ ，分表表示给定图像及策略矩阵的维度

接下来

$H$ 行输入图像矩阵

$K$ 行输入策略矩阵

输出描述

输出最大能量值

样例1

输入

1 1 1 1
5
1

输出

5.0

说明

有且仅有一条路径，最大能量值为 $5*1$ 为 $5.0$

样例2

输入

输出

119.0

说明

输入第一行是一个 $3×3$ 的图像以及 $3×3$ 的策略矩阵

每个位置的能量图：

$[[12.21.16.]$

$[30.50.36.]$

$[33.50.34.]]$

最大能量路径的值： $119.0$ 最大能量路径： $(2,0)->(1,1)->(1,2)$

提示

$1.$ 策略矩阵为奇数，边缘处用零填充

$2.$ 输出保留一位小数

输入

预期输出（选填）

思路

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

题目内容

输入描述

输出描述

样例1

样例2

提示

Status

Development

Support

About