标签： 线段树

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

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

考虑DP。

错误转移1

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

是的，又是一道考试时想出正解没有打出来的题目

货物分组 – 牛客网

根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：$$dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\}$$，初值有$dp(0, 0) = 0$，应求得$\min\limits_{j \in [1, n]} dp(n, j)$。

（更多…）