解题思路

题意：在一个仅能“向右/向下”行走的网格中，进入房间需要支付该房间的“进入成本”；另外最多可使用 k 次传送，从当前房间可零成本传送到任意进入成本 ≤ 当前房间进入成本的房间；传送落地不扣费（样例已验证），起点不计入成本。求到达右下角的最小总费用。

关键观察：

• 行走仅向右/下，图是一个 DAG；对固定“传送使用次数”这一层，行走的最短费用可用一次从左上到右下的顺序 DP 完成（每格只来自它的上/左）。
• 传送从代价为 c 的任意格，零费用到所有代价 ≤ c 的格。这等价于：若把“使用了 t 次传送”的层记为 t，则

题目内容

勇者小明被困在一座 $m$ 行 $n$ 列的地牢中，地牢的每个房间 $(i,j)$ 都标注了 “进入成本”（单位：金币）—— 进入该房间需消耗对应数量的金币。小明的初始位置是地牢左上角的房间 $(0,0)$，目标是到达右下角的宝藏房间 $(m - 1,n - 1)$，并尽可能减少金币消耗。

小明拥有两种移动方式：

• 常规行走：从当前房间 $(i,j)$ 只能向右走到 $(i,j + 1)$ 或向下走到 $(i + 1,j)$，进入目标房间后，需支付该房间标注的金币（即消耗等于目标房间的 “进入成本”）；
• 传送卷轴：小明最多可使用 $k$ 次传送卷轴。使用时，可从当前所在房间 $(i,j)$ 直接传送到任意满足 “目标房间进入成本 $≤$ 当前所在房间进入成本” 的房间 $(x,y)$，传送过程不消耗任何金币（成本为 $0$）。

请计算小明从起点到达宝藏房间的最小金币消耗总量。

输入描述

第一行依次输入 $m，n，k$ 接下来的 $m$ 行，每行输入 $n$ 个数字

输出描述

如果小明无法到达宝藏房间，输出 $-1$，否则输出最小金币消耗总量

补充说明

• $2≤m,n≤100$
• $m==grid.length$
• $n==grid[i].length$
• $0≤grid[i][j]≤100$，整数
• $0≤k≤10$
• 起点不计入成本

样例1

输入

3 4 1
1 3 2 5
2 1 4 2
5 3 1 5

输出

5

说明

说明 $m=3，n=4$ ，最多传送次数 $k=1$ 。最优路径为

1. 初始位置 $[0, 0]$

2. 传送到 $[2, 2]$，传送不产生消耗，成本为 $0$

3. 再从 $[2, 2]$ 走到 $[2, 3]$，成本为 $5$

   结果输出为 $5$