标签 - 单调队列

? 解题记录 ? ? 洛谷 ? ? 单调队列 ?    2018-10-21 15:09:42    466    0    0
题目描述为了增添公园的景致,现在需要在公园中修筑一个花坛,同时在画坛四周修建一片绿化带,让花坛被绿化带围起来。 如果把公园看成一个M*N的矩形,那么花坛可以看成一个C*D的矩形,绿化带和花坛一起可以看成一个A*B的矩形。 如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和,那么, 绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度 为了使得绿化带的生长得旺盛,我们希望绿化带的肥沃度最大。 输入输出格式输入格式:  第一行有6个正整数M,N,A,B,C,D 接下来一个M*N的数字矩阵,其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度
? 解题记录 ? ? 单调队列 ? ? 动态规划 ? ? 杂OJ ?    2018-03-24 15:03:16    782    0    0
题目描述输入一个长度为n的整数序列,从中找出一段不超过M的连续子序列,使得整个序列的和最大。例如 1,-3,5,1,-2,3当m=4时,S=5+1-2+3=7当m=2或m=3时,S=5+1=6 输入格式第一行两个数n,m第二行有n个数,要求在n个数找到最大子序和 输出格式一个数,数出他们的最大子序和 提示数据范围:100%满足n,m<=300000 样例数据输入样例 #1输出样例 #16 4 1 -3 5 1 -2 37本题我们要找一个不超过M长度的和最大的子段(可以不取)。那么直接把所有前缀和求出来,For一遍每一个右端点,用单调队列维护一下前面m个以内最小的前缀和是多少就
? 解题记录 ? ? 单调队列 ? ? 洛谷 ?    2018-03-22 10:10:42    456    0    0
题目描述现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 例如: The array is [1 3 -1 -3 5 3 6 7], and k = 3. 输入输出格式输入格式:   输入一共有两行,第一行为n,k。 第二行为n个数(<INT_MAX).   输出格式:   输出共两行,第一行为每次窗口滑动的最小值 第二行为每次窗口滑动的最大值   输入输出样例输入样例#1: 复制8 3 1 3 -1 -3 5 3 6 7 输出