相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4380
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/5271139.html
神犇题解Ⅱ：http://www.cnblogs.com/DaD3zZ-Beyonder/p/6052067.html
解题报告
首先不难发现第$i$个人的贡献只与 $\min ({p_j}|j \in [{a_i},{b_i}])$ 有关
于是我们考虑记录 $f(l,r,mn)$ 表示处理完区间 $[l,r]$ 的所有人，且区间最小值为 $mn$ 的总花费是多少
然后怎么进行转移，我就没有想出来了，总想着要把一个单调栈给搞到状态里 QwQ
看了题解以后，真的是只差一点点啊！
现在来说一说正解。设$g(i,j)$表示覆盖第$i$个门店，$c_k \ge j$的人有多少个
我们枚举区间最小值的位置$pos$，那么 $f(l,r,mn) = \max (f(l,pos – 1,x) + f(pos + 1,r,y) + g(pos,mn) \times mn|x,y \ge mn)$
于是我们记录一个$f$的后缀最小值什么的，就可以在 $O({n^3}m)$ 的时间复杂度内解决这个问题啦！
至于打印方案，我们记录一下每个状态的来源，然后逆向DFS回去输出就可以啦！
What i do not realize is in truth how you’re now not actually a lot more neatly-liked than you may be right now. You are very intelligent. You realize therefore significantly when it comes to this topic, produced me individually consider it from numerous varied angles. Its like men and women don’t seem to be involved except it is something to do with Girl gaga! Your individual stuffs nice. All the time take care of it up!
Do you mind if I quote a few of your articles as long as I provide credit and sources back to your blog? My blog is in the very same niche as yours and my users would genuinely benefit from some of the information you present here. Please let me know if this okay with you. Thanks!