标签 - 单调栈

? 解题记录 ? ? 洛谷 ? ? 单调栈 ? ? 模拟 ?    2018-10-29 23:30:59    635    0    0
题目描述 输入输出格式输入格式:   第一行有一个整数N(3<N<2000),表示登陆地带的大小是2×N。随后的两行每一行有N个整数(其绝对值不超过10^6),表示对应的矩形土地的适用度评估值,各个整数之间用一个空格隔开。   输出格式:   只有一行输出,为整数M,即所确定的实验基地的适用度。   输入输出样例输入样例#1: 复制4 -1 2 -3 4 5 6 7 8 输出样例#1: 复制31​  不知道为什么N会是2000而不是10^6。这道题
? 解题记录 ? ? 洛谷 ? ? 单调栈 ? ? 树状数组 ?    2018-10-10 07:51:50    459    0    0
题目描述有一个长度为n的字符串,每一位只会是p或j。求一个最长子串,使得不管是从左往右还是从右往左取,都保证每时每刻已取出的p的个数不小于j的个数。(1≤n≤1 000 000) 输入输出样例输入样例#1: 复制6 jpjppj 输出样例#1: 复制4​​   遇到个数有关的问题首先把j看做-1,p看做1。这样就是要从左往右从右往左每个位置的前缀和都非负,处理原数组[前/后]缀和为pre[i]、suf[i]。 考虑对于位置i,先分别处理i向右最长能延伸到的地方和向左最长能延伸到的地方,记为R[i]和L[i]。这就相当于找到
? 解题记录 ? ? 洛谷 ? ? 单调栈 ?    2017-11-05 13:14:05    413    0    0
题目描述某地有 N 个能量发射站排成一行,每个发射站 i 都有不相同的高度 Hi,并能向两边(当 然两端的只能向一边)同时发射能量值为 Vi 的能量,并且发出的能量只被两边最近的且比 它高的发射站接收。 显然,每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受,特别是为了安 全,每个发射站接收到的能量总和是我们很关心的问题。由于数据很多,现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。 输入输出格式输入格式:  第 1 行:一个整数 N; 第 2 到 N+1 行:第 i+1 行有两个整数 Hi 和 Vi,表示第 i 个人发射站的高度和发射的能量值。 &n