解题思路

外卖小哥在网格上只能向“右/下”移动，进入某格的代价为该格的值；此外可以至多使用 k 次无人机，将当前位置一次性“跳转”到任意代价不大的格子（grid[x][y] ≤ grid[i][j]），该次移动费用为 0。

把问题视作在有向图上求最短路：

• 普通边：从 (i,j) 到右/下邻居，边权为邻居的值；
• 无人机边：从 (i,j) 到任意 grid[x][y] ≤ grid[i][j]，边权为 0，最多使用 k 次。

题目内容

给定一个$m×n$的二维数组$grid$表示地图，数组每个值代表该点的通行成本，给定$k$表示可以使用无人机配送次数。

现有一个外卖小哥，从$(0，0)$位置出发，要送餐到$(m-1,n-1)$位置，有两种方式可以配送:

$1.$按规则配送:可以从当前区域向右或向下一格，配送成本为目标点的通行成本;

$2.$无人机配送:可从任意区域(i,j)调用无人机将餐品送到任意通行成本不大于$(i,j)$ 的区域$(x,y)$，即$grid[x][y] <= grid[i][j]$，此方式配送成本为$0$，但至多使用$k$次。

请你计算返回最小总配送成本

输入描述

第一行输入三个整数，表示$m,n,k$

以后$m$行每行$n$个整数，表示$grid$

输出描述

输出一个整数表示最小总配送成本

样例1

输入

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

输出

7

提示

$1 <= k <= n <= 100$

$n = grid[i].length$

$0 <= grid[i][j]<= 10^9$