题解：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)。