1 条题解
-
0
因为感受值都是大于等于0的，所以可以考虑如果i是区间里感受值最小的一天，找出这个区间左边界的最小值L[i]和右边界的最大值R[i]，让区间的感受值之和尽可能大。
计算L[i]时，我们从小到大枚举i，并维护一个感受值递减的单调队列，这样当i进队时，没有被弹出的队尾的那个元素，就是1~i-1中满足感受值比i的感受值大的最大下标，也就是L[i]-1。
用类似的方法，从大到小枚举i，计算出R[i]之后，我们就可以用L[i]~R[i]的感受值之和，乘上i的感受值（作为区间里最小的感受值），去更新答案了。
核心代码
a[0] = a[n+1] = 0 ; tail = 1; head = 1; q[1] = 0; for(int i = 1;i <= n;i ++) { while(head <= tail && a[q[head]] >= a[i]) tail--; l[i] = q[tail] + 1; q[++tail] = i; } tail = 1; head = 1; q[1] = n+1; for(int i = n;i >= 1;i --) { while(head <= tail && a[q[head]] >= a[i]) tail--; r[i] = q[tail] - 1; q[++tail] = i; }
- 1