【题解】CF1416E Split
2021/10/7 23:15:37
本文主要是介绍【题解】CF1416E Split,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
考虑令 \(f_{i,j}\) 表示前 \(i\) 个数,\(b\) 的最后一个是 \(j\) 时最小段数。转移:
\[f_{i,j}=[j\not=a_i-j]+\min_{1\leq k< a_{i-1}}\left(f_{i-1,k}+[a_i-j\not=k]\right) \]注意到后面的转移,如果 \(f_{i-1,a_i-j}\) 不是最小值,那么从最小值转移不会更劣。
用 set 维护所有最小值的位置,然后再维护一个最小值的值。注意同时需要考虑所有状态都是最小值的情况,需要额外记 \(l,r\) 表示 \([l,r]\) 区间的状态同样也是最小值。
至于下标从 \(k\) 变成 \(a_i-k\) 可以考虑记录 \(A,B\),每个数 \(x\) 的实际值为 \(A+B\times x\),这样就只需要修改 \(A,B\) 了。
记得开 long long
,虽然我也不知道为什么要开 long long
,但是不开就 wa on 8 了 ...
代码:Submission #131074597 - Codeforces
这篇关于【题解】CF1416E Split的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享