区间DP

题意给定 $n$ 个线段，每个线段有一个权值 $w_i$，每次取轴上一点，获得的权值为选择的覆盖在当前点上的线段的最大权值，求最终覆盖所有线段后需要的最小权值 题解好吧是一道非常水的区间 $dp$ 然而我并没有想出来所以我是真的绝望 先把 $l_i, r_i$ 离散化后令 $f_{l, r}$ 表示完全覆盖区间 $[l, r]$ 的线段的最小权值，设完全处于 $[l, r]$ 的线段中权值取最大值的线段 $p$，则有转移方程$$f_{l, r} = \min \{f_{l, k - 1} + f_{k + 1, r} + w_p\} (l_p \le k \le r_p)$$所以注意一定要完全覆盖，$[l, k - 1], [k + 1, r]$ 才不会对 $[l, r]$ 造成影响，于是我就卡这儿了 谨以此文纪念我逝去的智商 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 ...