AT_ahc049_a.[AHC049A] Durability-Constrained Transport

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

有一个 $N \times N$ 的办公室。左上角的格子的坐标为 $(0, 0)$ ，向下走 $i$ ，向右走 $j$ 的位置坐标为 $(i, j)$ 。格子 $(0, 0)$ 是办公室的出入口。

初始状态下，除出入口外的所有格子上都各放有一个纸箱。每个纸箱有两个属性：重量和 耐久力。位于格子 $(i, j)$ 的纸箱重量为 $w_{i,j}$ ，耐久力为 $d_{i,j}$ 。

纸箱可以上下叠放，这样可以一次搬运多个纸箱。高桥社长的目标是从初始位置 $(0,0)$ 出发，反复进行如下操作，将所有纸箱搬出办公室：

拿起当前位置的纸箱。如果已经拿着纸箱，则把新纸箱放在最上面。如果当前位置没有纸箱，则无法进行此操作。
将手中最上面的纸箱放在当前位置。如果当前位置已经有纸箱，则无法进行此操作。
向上下左右相邻的格子移动。可以移动到有纸箱的格子，但不能走出办公室（即不能超出 $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
执行操作2时：2
执行操作3时：根据移动方向，上：U，下：D，左：L，右：R

设操作总数为 $L$ ，请按如下格式输出：

$a_0$
$\vdots$
$a_{L-1}$

查看示例

输入输出样例

输入#1

20
0 3 749 809 20 263 83 30 559 8 5 269 675 47 235 204 747 216 134 244
2 651 130 557 93 426 690 873 506 98 22 251 213 814 874 79 857 6 158 639
2 965 45 107 259 20 957 244 18 962 152 82 327 226 24 131 99 1 255 60
177 1 42 878 353 185 89 656 757 54 351 349 489 249 679 756 191 395 719 145
613 203 741 455 1 402 877 791 146 956 506 262 280 746 156 733 66 237 389 115
164 738 84 747 10 579 81 6 78 215 337 556 479 498 2 674 120 737 429 106
872 394 35 325 49 6 129 185 45 218 18 892 162 7 419 579 768 11 724 266
29 236 832 372 132 857 840 10 446 74 734 199 148 802 24 467 321 410 237 50
715 391 412 13 312 2 138 645 333 260 621 736 483 876 62 9 44 77 180 3
165 852 738 29 110 119 857 974 104 103 886 500 271 819 155 467 579 108 466 837
243 39 711 197 494 17 800 721 15 193 138 5 451 736 311 272 582 177 112 533
441 65 2 544 545 259 147 10 101 411 23 144 449 18 668 211 497 475 470 867
179 661 8 73 600 371 374 417 150 629 520 236 625 508 168 733 36 282 427 121
534 715 558 187 707 714 368 882 437 607 27 18 15 988 306 198 130 343 70 42
248 257 714 3 133 859 658 52 385 487 572 25 211 485 381 453 198 496 576 7
18 89 103 218 494 679 981 133 59 69 73 397 517 567 542 8 619 13 247 373
355 745 81 291 401 142 357 244 7 581 440 6 963 173 750 763 1 382 278 5
275 103 7 843 2 14 86 374 97 218 15 319 55 503 886 44 27 228 375 796
430 146 873 39 5 714 366 732 679 369 642 344 978 237 230 98 273 98 58 850
266 608 739 2 190 592 194 84 611 14 101 909 4 582 122 12 122 994 635 916
0 89 10274 11922 300 6685 978 640 13718 132 143 7028 18239 1327 6881 2284 21156 2760 1998 5070
57 17805 2901 14519 1693 10841 11743 18976 9379 2092 285 3524 5983 16567 22972 1063 19938 131 4309 15177
40 21359 1207 2121 3421 233 27186 6872 310 11251 3786 1176 5352 4669 644 2427 1063 16 5886 1000
3615 18 918 12387 7059 4315 2057 15533 15664 1195 10141 8595 5218 6993 10755 19254 2432 9972 20357 3718
8450 3919 8454 5988 19 10140 12007 18903 3935 18739 11371 4330 3194 11908 1710 15085 1585 6893 5701 1207
2641 20082 1007 20670 242 16408 821 174 1941 6053 5509 10545 11073 13932 58 9389 3431 10249 5398 2521
19054 4835 829 4674 1201 126 2364 3885 858 5383 501 21304 4520 180 5604 9931 21101 168 19471 5338
712 5765 11653 9607 2457 18495 9954 105 11699 818 16356 3906 1654 10149 438 13133 7833 4447 5445 1326
10666 6309 4688 285 5169 40 1404 18295 3541 7125 8287 20290 8837 17858 1621 135 1115 1091 3288 54
2597 9955 16763 471 2335 1574 14642 16187 2376 1887 24636 5641 7433 17306 2957 6663 5966 3044 5358 9769
5905 611 17099 3300 11161 385 15895 19522 435 2108 3650 141 8058 21485 3988 2737 16273 4105 2571 11724
7296 1489 51 6519 5911 3647 2533 236 1190 4266 500 3338 7312 385 19463 4942 10835 11174 10700 9738
4477 16314 165 805 17700 4016 7057 12420 2756 17887 6796 5143 12927 6174 4740 20452 424 3101 11615 2445
13368 15983 15135 5582 12578 15525 4649 24252 6902 17168 460 228 413 23337 8237 3631 3838 6815 1706 1166
6713 5548 10910 65 1426 17897 8171 886 5466 8932 7274 277 2969 12341 10707 10334 2143 12639 7016 144
462 1829 1530 6394 14306 7206 16721 3469 1058 1201 1641 7989 7068 8612 8485 197 8113 306 6585 6213
4014 13889 2016 7397 6739 3985 10474 2701 107 8285 5588 90 10340 2717 16467 20426 22 9518 5965 124
6569 2065 136 23365 25 276 992 8245 1736 4797 316 6097 712 9186 25794 1282 431 3350 8782 9615
9031 3928 13928 394 118 18798 6870 18849 8115 10434 8884 3992 29004 6921 3450 2052 5705 2732 837 18597
6226 15329 13644 58 3923 10666 4191 1802 18180 242 2764 13987 101 10450 1509 311 1638 19358 11533 16943

输出#1

D
R
1
R
R
1
U
1
L
1
L
1
L
R
R
R
R
R
R
R
R
1
D
1
L
1
L
1
L
1
L
1
2
L
2
U
2
L
2
L
L
R
R
1
R
1
D
1
L
1
L
L
1
U

说明/提示

故事背景

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))$ 。

工具（输入生成器与可视化工具）

网页版：功能更强，支持动画和手动操作。
本地版：需安装 Rust 语言编译环境。
- Windows 版编译好的可执行文件：不想搭建 Rust 环境可用此版本。

比赛期间禁止分享可视化结果、解法或思路。请注意遵守规则。

由 ChatGPT 4.1 翻译

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

首页