计蒜客 38228 – Max answer

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

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

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

 

 

1
说点什么

avatar
50
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 参考我的ICPC 2019 南昌邀请赛网络预赛,计蒜客38228 Max answer 题解。 […]