CF 67 C. Sequence of Balls
2021/8/11 23:36:49
本文主要是介绍CF 67 C. Sequence of Balls,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CF 67 C. Sequence of Balls
首先可以发现\(2t_e\geq t_i+t_d\)。
首先可以发现每一个元素最多会被换一次。
而且可以发现操作按照某一个顺序是最优的:
- 删除
- 交换
- 添加
- 替换
设\(dp_{i,j}\)表示考虑了\(a\)的前\(i\)个变成了\(b\)的前\(j\)个的答案。
比较难处理的是:
- 删除\([x+1,y-1]\)
- 交换\(x,y\)
- 在\(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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享