首页 > Cleaning Shifts
开通博客写题解
头像 Dear㉿You
发表于 2020-10-23 15:12:17
Cleaning Shifts 分析 此类问题似被统称为——最小区间覆盖问题。首先考虑最简单的转移方程表示覆盖[1,b[i]]的区间的最小代价。考虑优化——快速找到区间最小值。只需要建立一棵线段树，每次查询对应区间，更新。 代码 //#pragma GCC optimize(3,"inlin 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 louhc
发表于 2019-08-25 22:05:09
思路 先将所有左边界-1,也就是将所有"块"变成"点",从"第l块到第r块"到"坐标之间的块",方便离散化.先对所有区间按右边界排序,枚举每个区间,更新答案大家可能发现我的转移方程与算法竞赛进阶指南上不太一样,因为我的表示方式不同,书上表示覆盖第1块到第i块都被覆盖过的最优答案,而我是坐标从到之间所 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”