[AHC023A] Crops on Grid 题解

· · 题解

分数 / 排名：使用该解法可以在 System Test 中获得 1047323350 分，最终排名 378/800。

考虑给机械留出一个通道使得它可以直接到达每一块农田，这样虽然损失了一些分数，但是不需考虑地被塞住没法种植 / 收成的问题。这一步可以使用随机化爬山法循环多次得到答案，具体地就是确定一个田地的排列，然后每次随机扰动几个位置的数，如果更优就更新。

再考虑给每一块农田分配作物。可以使用两种方法分配，一种是朴素的从左端点最小的选起，每次寻找在当前情况下可以放入的左端点最小的作物；另一种是倒着做一遍背包。两种情况取较优者即可。

提交记录：Submission #45448820。