CodeForces Round #755 Div.2 F / Div.1 D Serious Business
此题整整困了我一天半,耗费了好几张草稿纸。实在走投无路,翻看题解,却发现正解曾经近在咫尺。有必要稍作整理。
考虑DP。
错误转移1
这道题与清理班次(《算法竞赛进阶指南》上的一道例题)过于相似,都是“给定一些段落,选择其中一些完整覆盖,求最小花费”的形式。记上述花费为。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在位置从第行转到第行,利用数据结构维护所有,在转移到第二行,解锁到达的最小代价。对于各行前缀和,我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在的时间内,计算出对于一个固定的起点,所有的值。 (更多…)