C/C++教程

CF 67 C. Sequence of Balls

本文主要是介绍CF 67 C. Sequence of Balls，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CF 67 C. Sequence of Balls

首先可以发现\(2t_e\geq t_i+t_d\)。

首先可以发现每一个元素最多会被换一次。

而且可以发现操作按照某一个顺序是最优的：

  1. 删除
  2. 交换
  3. 添加
  4. 替换

设\(dp_{i,j}\)表示考虑了\(a\)的前\(i\)个变成了\(b\)的前\(j\)个的答案。

比较难处理的是：

  1. 删除\([x+1,y-1]\)
  2. 交换\(x,y\)
  3. 在\(y,x\)中间添加一些元素

这时候需要观察一个很重要的性质：

交换\(x,y\)就一定不会修改。

因为：

\(te+tr\geq td+tr\and te+tr\geq tr+tr\)

同时\(te\geq \frac{td+tr}{2},te\geq tr\)。

然后贪心交换到最近的就可以了。

这篇关于CF 67 C. Sequence of Balls的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航