分治

CodeForces Round #755 Div.2 F / Div.1 D Serious Business

此题整整困了我一天半,耗费了好几张草稿纸。实在走投无路,翻看题解,却发现正解曾经近在咫尺。有必要稍作整理。

考虑DP。

错误转移1

这道题与清理班次(《算法竞赛进阶指南》上的一道例题)过于相似,都是“给定一些段落[lp,rp][l_p, r_p],选择其中一些完整覆盖[l0,r0][l_0,r_0],求最小花费”的形式。记上述花费为f(l0,r0)f(l_0, r_0)。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在x2x_2位置从第22行转到第33行,利用数据结构维护所有x1x2x_1\leq x_2,在x1x_1转移到第二行,解锁到达x2x_2的最小代价。对于各行前缀和,我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在O(nlogn)\mathrm{O}(n \log n)的时间内,计算出对于一个固定的起点l0l_0,所有f(l0,r0),r0[l0,n],p,rp=r0f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0的值。 (更多…)

More
  • 2022年3月8日