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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!