题解：AT_arc087_b [ABC082D] FT Robot

其实并不需要 DP。

将水平与竖直的移动分开处理，问题转化成给定序列 $a_i$ 与常数 $x$，判断是否存在序列 $c_i \in \{-1,1\}$ 使 $\sum_{i=1}^{n}{a_ic_i}=x$。

考虑贪心，将 $a_i$ 从大到小排序后凑 $x$，如果当前答案比 $x$ 大就减去 $a_i$，反之加上 $a_i$。归纳配合邻项交换易证该策略凑出的数最接近 $x$，保证了判断正确性。复杂度 $O(n \log n)$。