AT_zone2021_e.潜入

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个二维平面，你现在位于坐标 $(1, 1)$ ，想要移动到 UFO 所在的坐标 $(R, C)$ 。
当你在 $(r, c)$ 时，你可以进行以下 $4$ 种移动：

从 $(r, c)$ 移动到 $(r, c + 1)$ ，花费 $A_{r, c}$ 的代价。该移动仅当 $c < C$ 时可以使用。
从 $(r, c)$ 移动到 $(r, c - 1)$ ，花费 $A_{r, c - 1}$ 的代价。该移动仅当 $c > 1$ 时可以使用。
从 $(r, c)$ 移动到 $(r + 1, c)$ ，花费 $B_{r, c}$ 的代价。该移动仅当 $r < R$ 时可以使用。
选择一个满足 $1 \leq i < r$ 的整数 $i$ ，从 $(r, c)$ 移动到 $(r - i, c)$ ，花费 $1 + i$ 的代价。

请你求出从 $(1, 1)$ 移动到 $(R, C)$ 所需的最小代价。

输入格式

输入按以下格式从标准输入读入。

$R$ $C$
$A_{1,1}$ $\cdots$ $A_{1,C-1}$
$\vdots$
$A_{R,1}$ $\cdots$ $A_{R,C-1}$
$B_{1,1}$ $\cdots$ $B_{1,C}$
$\vdots$
$B_{R-1,1}$ $\cdots$ $B_{R-1,C}$

输出格式

输出答案。

输入输出样例

输入#1
```
3 3
10 1
10 10
1 10
1 10 1
1 10 1
```
输出#1
```
9
```

输入#2

7 11
42 77 94 76 40 66 43 28 66 23
27 34 41 31 83 13 64 69 81 82
23 81 0 22 39 51 4 37 84 43
62 37 82 86 26 67 45 78 85 2
79 18 72 62 68 84 69 88 19 48
0 27 21 51 71 13 87 45 39 11
74 57 32 0 97 41 87 96 17 98
69 58 76 32 51 16 38 68 86 82 64
53 47 33 7 51 75 43 14 96 86 70
80 58 12 76 94 50 59 2 1 54 25
14 14 62 28 12 43 15 70 65 44 41
56 50 50 54 53 34 16 3 2 59 88
27 85 50 79 48 86 27 81 78 78 64

输出#2

输入#3

输出#3

说明/提示

故事

在推进密码解读的过程中，你的伙伴 Moore 突然被 UFO 吸走了。Moore 几乎是独自一人开发了与 UFO 通信的系统，如果这样下去就无法与 UFO 通信了！
你回想起黑心初创公司时代的死亡冲刺。巴士因子 $=1$ 的团队总是很脆弱。
没办法，只能亲自进入 UFO 内部与其对话了。你抬头望去，发现 UFO 放下了类似梯子的东西。
但仔细一看，梯子已经破烂不堪，部分地方已经腐烂脱落。你必须想办法巧妙地攀爬上去。

约束条件

所有输入均为整数。
$2 \leq R, C \leq 500$
$0 \leq A_{i,j} < 10^3$
$0 \leq B_{i,j} < 10^3$

样例解释 1

如下移动可以达到总代价 $9$ ：

从 $(1, 1)$ 移动到 $(2, 1)$ ，花费 $1$ 。
从 $(2, 1)$ 移动到 $(3, 1)$ ，花费 $1$ 。
从 $(3, 1)$ 移动到 $(3, 2)$ ，花费 $1$ 。
从 $(3, 2)$ 移动到 $(1, 2)$ ，花费 $3$ 。
从 $(1, 2)$ 移动到 $(1, 3)$ ，花费 $1$ 。
从 $(1, 3)$ 移动到 $(2, 3)$ ，花费 $1$ 。
从 $(2, 3)$ 移动到 $(3, 3)$ ，花费 $1$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页