AT_ahc049_a [AHC049A] Durability-Constrained Transport

AtCoder社は、新しいオフィスへ移転することにした。 コストを抑えるため、引っ越し業者には頼らず、高橋社長自ら荷物の運び出しを行うことになった。 旧オフィス内には大量のダンボール箱が平積みされており、それらをすべて出入り口まで運び出す必要がある。 ダンボール箱は積み重ねて複数同時に運ぶことができるが、重ねすぎると重さに耐えきれず潰れてしまう可能性がある。 できるだけ少ない移動回数で、すべての箱を無事に運び出す方法を考えてほしい。

有一个 $N \times N$ 的办公室。左上角的格子的坐标为 $(0, 0)$，向下走 $i$，向右走 $j$ 的位置坐标为 $(i, j)$。格子 $(0, 0)$ 是办公室的出入口。 初始状态下，除出入口外的所有格子上都各放有一个纸箱。每个纸箱有两个属性：**重量** 和 **耐久力**。位于格子 $(i, j)$ 的纸箱重量为 $w_{i,j}$，耐久力为 $d_{i,j}$。 纸箱可以上下叠放，这样可以一次搬运多个纸箱。高桥社长的目标是从初始位置 $(0,0)$ 出发，反复进行如下操作，将所有纸箱搬出办公室： 1. 拿起当前位置的纸箱。如果已经拿着纸箱，则把新纸箱放在最上面。如果当前位置没有纸箱，则无法进行此操作。 2. 将手中最上面的纸箱放在当前位置。如果当前位置已经有纸箱，则无法进行此操作。 3. 向上下左右相邻的格子移动。可以移动到有纸箱的格子，但不能走出办公室（即不能超出 $N \times N$ 的范围）。 高桥社长力气很大，可以一次拿任意重的纸箱。然而，手中纸箱的耐久力会在每次移动（操作3）时减少。耐久力降到 $0$ 或以下的纸箱会被压坏，判定为 WA。 耐久力的减少量等于该纸箱上方所有纸箱的总重量。也就是说，假设手中纸箱从下到上的重量为 $w_1, w_2, \ldots, w_n$，那么从下往上第 $i$ 个纸箱每次移动时耐久力减少 $\sum_{j=i+1}^n w_j$。 只有在移动（操作3）时耐久力才会减少，操作1和操作2不会影响耐久力。操作2放下纸箱后，耐久力不会恢复。 每当通过操作3回到出入口 $(0,0)$ 时，手中所有纸箱都会被搬出办公室。 最多可以进行 $2\times N^3$ 次操作。请尽量用最少的移动次数将所有纸箱搬出办公室。

输入通过标准输入给出，格式如下： > $N$ $w_{0,0}$ $\cdots$ $w_{0,N-1}$ > $\vdots$ > $w_{N-1,0}$ $\cdots$ $w_{N-1,N-1}$ > $d_{0,0}$ $\cdots$ $d_{0,N-1}$ > $\vdots$ > $d_{N-1,0}$ $\cdots$ $d_{N-1,N-1}$ - 所有测试用例中，$N=20$。 - $w_{i,j}$ 表示格子 $(i, j)$ 上纸箱的重量。$(0,0)$ 没有纸箱，所以 $w_{0,0}=0$，其余格子满足 $1 \leq w_{i,j} \leq 10^3$。 - $d_{i,j}$ 表示格子 $(i, j)$ 上纸箱的耐久力。$(0,0)$ 的 $d_{0,0}=0$，其余格子满足 $10 \leq d_{i,j} \leq 3\times 10^4$。

第 $t$ 步的操作用一个字符 $a_t$ 表示，具体如下： 1. 执行操作1时：`1` 2. 执行操作2时：`2` 3. 执行操作3时：根据移动方向，上：`U`，下：`D`，左：`L`，右：`R` 设操作总数为 $L$，请按如下格式输出： > $a_0$ > $\vdots$ > $a_{L-1}$ [查看示例](https://img.atcoder.jp/ahc049/LDUZCjLO.html?lang=ja&seed=0&output=sample)

## 故事背景 AtCoder 公司决定搬到新办公室。为了节省成本，没有请搬家公司，而是由高桥社长亲自搬运所有物品。 旧办公室里堆满了纸箱，需要全部搬到出入口。纸箱可以叠放一起搬，但叠得太高会压坏下面的纸箱。 请思考如何用尽量少的移动次数，安全地将所有纸箱搬出。 ## 得分 设操作3（移动）的次数为 $T$，办公室内剩余纸箱数为 $R$，则得分如下： - 若 $R>0$，得分为 $N^2-R$。 - 若 $R=0$，得分为 $N^2+2\times N^3-T$。 其中 $T$ 只统计操作3（移动）的次数，操作1（拿起）和操作2（放下）不计入 $T$。但所有操作总数不得超过 $2\times N^3$。 总共有 150 个测试用例，所有测试用例得分之和为最终得分。若有任意测试用例输出不合法或超时，整份提交判为 WA 或 TLE。最终排名以比赛期间最高得分为准，赛后不再进行系统测试。得分相同者排名并列。 ## 输入生成方法 - $\mathrm{rand\_double}(L,U)$：在 $[L, U]$ 区间内均匀随机生成实数。 ### $w$ 的生成 对除 $(0,0)$ 外的每个格子 $(i,j)$，$w_{i,j} = \mathrm{round}(\mathrm{rand\_double}(1, \sqrt{1000})^2)$。 ### $d$ 的生成 对除 $(0,0)$ 外的每个格子 $(i,j)$，$d_{i,j} = \mathrm{round}(w_{i,j} \times \mathrm{rand\_double}(10, 30))$。 ## 工具（输入生成器与可视化工具） - [网页版](https://img.atcoder.jp/ahc049/LDUZCjLO.html?lang=ja)：功能更强，支持动画和手动操作。 - [本地版](https://img.atcoder.jp/ahc049/LDUZCjLO.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版编译好的可执行文件](https://img.atcoder.jp/ahc049/LDUZCjLO_windows.zip)：不想搭建 Rust 环境可用此版本。 比赛期间禁止分享可视化结果、解法或思路。请注意遵守规则。 由 ChatGPT 4.1 翻译