题目大意：
两个硬币，给定初始位置a和b，q次操作，每次操作可将其中的任意一个移到位置x，代价为距离。所有位置在1-n之间。求最小代价。
n,q<=2e5
题目解法：
最朴素的状态f[i][j][k]表示i次操作后两个硬币分别在j,k的最小代价。观察发现j,k中必有一个是这次操作中规定的移动到的位置，因此直接消掉一维，f[i][j]表示i次操作后一个硬币在j另个一个在x[i]的最小代价。向后更新显然是f[i+1][q[i]]=f[i][j]+|q[i+1]-j|,f[i+1][j]=f[i][j]+|q[i+1]-q[i]|。复杂度O(n^2)。50pts到手。
考虑继续优化转移。首先还是把状态转移方程改成从i-1转移过来的形式。我们可以得到以下两种等式：
//这里的q[i]就是上述的x[i]，手残写岔了
边界是f[0][a]=0,q[0]=b（直接把初始位置当做一次操作）
记得开long long
原文：https://www.cnblogs.com/myrcella/p/12904576.html