题解：AT_abc221_g [ABC221G] Jumping sequence

Expert_Dream · 2024-03-22 16:44:52 · 题解

这是我第一道正经的黑题，鼓掌！

这道题精妙在于将整个图旋转 45 度，虽然可能要画图，但我感觉不用画图也是可以理解的了。

为什么要旋转 45 度呢？

我们先把所有种类的操作的偏移量列出来。

• L(-d_i,0)
• R(d_i,0)
• U(0,d_i
• D(0,-d_i)

发现有三种可能的值，有点难搞，怎么办？如果将图旋转了一下，会发生什么呢？

• L(-d_i,-d_i)
• R(d_i,d_i)
• U(-d_i,d_i)
• D(d_i,-d_i)

这样，只有了 d_i 和 -d_i。

依然不太好搞。然后，我们可以将最终答案的横纵坐标减去 \sum_{i=1}^n d_i。这样，每一次的操作就变成了：

也就是说，每一次的操作横纵坐标都加上 d_i。

• L(0,0)
• R(2\times d_i,2\times d_i)
• U(0,2 \times d_i)
• D(2\times d_i,0)

这样，我们发现了横纵坐标是不会互相依赖的，都是独立的，我们可以对他们进行单独计算，最后拼起来即可。

如何计算能否拼成功呢？那么我们就用到可行性背包问题。

到最后，我们从后往前记录路径就可以了。

link。