数据结构：
数组：<有下标> 数据易查找 不易插入
链表：<无下标> 易插入 不易查找
邻接表 哈希表 卡常数题
——<结合> 块状链表:是将数组分成若干块，每一块的大小是O(pn) 的，块与块之间用链表串起来，而各种操作都是暴力维护.
队列：
普通队列：队首删除，队尾插入（队首/队尾指针++）
循环队列
双端队列：插入删除都既能在队首也能在队尾，实现也相当简单
单调队列
——基础应用：滑窗问题
一般来说，如果要求最小值，我们就维护一个单调递增序列，反之维护一个单调递减序列。
总结：对于给定一个数组，有m 组询问，每次询问一段区间的最值的题目，若询问区间按左端点排序后满足右端点单调递增，则可使用单调队列。
Bzoj2096：
给出一个长度为n个序列
要求找出最长的一段连续子序列，使得（最大值-最小值）<=k
N<=1000000
我们考虑顺序枚举序列的右端点 I
设在位置 i 处，取得最长合法序列的左端点为 L[i]
易证随着 i 的增加L[i]单调不减
于是开两个单调队列维护最大值和最小值即可
注意最优值是上一次弹出的队首的下一个位置
——优化动态规划：
有n 只奶牛，编号为1; 2;...; n，第i 只奶牛有个权值vi，你要选择一些奶牛，得到选择的奶牛权值之和的价值。但是选择的奶牛中在原数组不许有连续k 个。
O(nk) 的dp 是显然的：dp[i] = max(dp[j
评论 (0)
