AT_ahc034_a [AHC034A] Leveling with a Dump Truck
题目描述
现有一 $N \times N$ 的土地。定义 $(i,j)$ 为从上起第 $i+1$ 行,左起第 $j+1$ 列的单元格。
定义 $(i,j)$ 的高度为 $h_{i,j}$,保证各单元格高度之和为 $0$。
在最开始时,有一空挖掘机在 $(0,0)$ 处。你可以进行以下三种操作合计不超过 $100000$ 次:
- 往挖掘机上装 $d$ 单位的土。该操作代价是 $d$。
- 从挖掘机上卸下 $d$ 单位的土。该操作代价是 $d$。需要保证操作后挖掘机所装土的数量不为负数。
- 把挖掘机向上下左右其中一个方向移动一格。该操作代价是 $d+100$,其中 $d$ 表示挖掘机所装土的量。
试给出一个操作序列,让所有单元格高度变为 $0$,并使操作总代价最小。
输入格式
第一行一个数 $N$。
随后 $N$ 行,每行 $N$ 个数,代表各单元格初始高度。
输出格式
记 $T$ 为操作次数。
输出共 $T$ 行,每行一个操作。
+ 从当前位置将泥土装载 $d$ 单位到挖掘机上:`+d`
+ 将 $d$ 单位泥土从挖掘机卸到当前位置:`-d`
+ 将挖掘机移动到相邻的方格:`U`、`D`、`L` 和 `R`
说明/提示
保证 $N=20$ 且 $-100 \le h_{i,j} \le 100$。
[Web](https://img.atcoder.jp/ahc034/vImT4eac.html?lang=en):一个可视化工具。
translated by @[heyuguo](/user/66964)