计蒜客 38228 – Max answer

题目链接:计蒜客 38228 – ICPC 2019 南昌全国邀请赛(网络赛)I题

考虑每个点作为当前区间最小值时候的情况。如果这个点是负的,那么就在这个区间里找一个较小的和,相乘得到对答案的贡献,如果为正,则找一个较大的和。那么我们可以用线段树维护前缀和和后缀和的区间最大/最小值,当$i$是$[l,r]$中的最小值的时候,找$[i, r]$的前缀和最值,$[l,i-1]$的后缀最值,然后汇总答案。

整体思路如上,为了得到每个$i$对应的$l$和$r$,我们需要预处理出所有的点向左向右能到达的点,可以使用单调栈或者递推的方法,可以参考POJ 2796

 

 

说点什么

avatar
50
  Subscribe  
提醒