我爱喝旺仔

分类

题解(18)

/ 注册

全部文章（共1篇）

CF【1313C2】单调栈+魔改前缀和

题意给出n个数，第i个数为a[i]，要找到一个单峰序列b，其中b[i]<=a[i]，要使其和最大，输出序列之和最大情况下的b序列。题解对于a[i]用单调栈找一下它左边第一个小于它的数(记为l[i])和它右边第一个小于它的数(记为r[i])，然后分别统计一下左边的前缀和和右边的前缀和(此时的前缀...

单调栈前缀和

2020-10-10

2 553