题解：AT_abc221_g [ABC221G] Jumping sequence

这是我第一道正经的黑题，鼓掌！ 这道题精妙在于将整个图旋转 $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](https://atcoder.jp/contests/abc221/submissions/51451629)。