典题是 AT_abc221_g [ABC221G] Jumping sequence – 洛谷。

另一个典题 AT_abc240_g [ABC240G] Teleporting Takahashi – 洛谷。

本题中，题面要求我们解决两个事情：决策 $D_i$ 分配给横坐标还是纵坐标，以及加还是减。

这个显然是不好做的，这就可以引出一种常见 trick。

考虑把 $(X,Y)\to(X+Y,X-Y)$，这显然是一个双射，我们可以发现原来的操作变成了：

• 向上：$(X,Y)\to(X+D,Y-D)$
• 向下：$(X,Y)\to(X-D,Y+D)$
• 向左：$(X,Y)\to(X-D,Y-D)$
• 向右：$(X,Y)\to(X+D,Y+D)$

容易发现这样我们不再需要决策 $D_i$ 分配给谁，同时横纵坐标对于每个 $D_i$ 而言的加减情况完全独立，只需要分开解决即可，显然可以使用 bitset 优化背包。

事实上，$(X,Y)\to(X+Y,X-Y)$ 是一种经典的 trick（在曼哈顿与切比雪夫的互相转化中亦有记载），他的本质是通过把横纵坐标结合起来减少限制，当发现题目中横纵坐标互相限制时，可以尝试使用此技巧。