【BZOJ 4380】[POI2015] Myjnie

相关链接

题目传送门: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回去输出就可以啦!