思路

1. 预处理能量： 先按上式计算整张图的能量矩阵 $E$，复杂度 $O(H\cdot W\cdot K^2)$。

2. 动态规划建模： 用 $f_{i,j}$ 表示走到位置 $(i,j)$ 的最大能量和：

   • 边界： $f_{i,0}=E_{i,0}$，对所有 $i\in[0,H-1]$。
   • 转移：

题目内容

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

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

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

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

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

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

输入描述

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

接下来

$H$ 行输入图像矩阵

$K$ 行输入策略矩阵

输出描述

输出最大能量值

样例1

输入

1 1 1 1
5
1

输出

5.0

说明

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

样例2

输入

3 3 3 3
1 2 3
4 5 6
7 8 9
1 2 2
1 1 1
1 1 1

输出

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.$输出保留一位小数