Treasure Hunting

题目描述

有一个由 $H$ 行水平行和 $W$ 列垂直列组成的网格。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的方格。方格 $(i, j)$ 中写有一个整数 $A_{i,j}$。 Takahashi 将从 $(1, 1)$ 出发，不断向右或向下各移动一格，直到到达 $(H, W)$。不允许离开网格。 这次旅行的代价定义为：

在所经过的 $H+W-1$ 个方格上写的整数中取最大的 $K$ 个整数之和。

求可能的最小代价。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $K$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$ $\vdots$ $A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$

输出格式

输出答案。

1 3 2
3 4 5

9

2 2 1
3 2
4 3

3

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

21

提示

$1 \leq H,W \leq 30$ 1 \leq K < H+W $1 \leq A_{i,j} \leq 10^9$ 输入中的所有数值均为整数。只有一种行走方式，所经过的方格上的整数从大到小分别为 $5$、$4$、$3$，因此我们输出 $9(=5+4)$。
最小代价通过按顺序经过 $(1,1)$、$(1,2)$、$(2,2)$ 来实现。

标签: AtCoder|abc227F

来源

AtCoder|abc227F