1D Party 题解 我们可以将原来的序列随时间变化转化成一个图像，纵轴代表时间，横轴代表 A A A的值。 那么我们可以得到这样一个图像： 其中不同颜色代表不同的点的运动路径。 由于要最优，我们肯定要让每个点都一直处于运动状态，我们发现每个点大概有一下两种运动状态： 先向左走直到与另一个点相遇，再一直向右走。先向右走直到与另一个点相遇，再一直向左走。 无论如何，与别的点相遇

https://www.luogu.com.cn/problem/AT_arc120_e 考虑二分时间，然后设 d p ( i , 0 ) dp(i,0) dp(i,0) 表示第 i i i 个人开头往左走，掉头后剩余步数。 d p ( i , 1 ) dp(i,1) dp(i,1) 表示第 i i i 个人先往右走，最多走多少步就有掉头。 然后在纸上画一画就是小学的相遇问题，直接转移即