#0009. 移动硬币

题目大意:

  两个硬币,给定初始位置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],手残写岔了#0009. 移动硬币

 

  边界是f[0][a]=0,q[0]=b(直接把初始位置当做一次操作)

  记得开long long

#0009. 移动硬币

上一篇:解决苹果手机绑定小米手环4支付宝,蓝牙无法连接问题。


下一篇:未找到 app.json 中的定义的 pages "pages/category/index" 对应的 WXML 文件的解决方案