滑动窗口,区间dp

张开发
2026/4/23 16:59:13 15 分钟阅读

分享文章

滑动窗口,区间dp
昨天写了两道题一道是滑动窗口一道是区间dp。第一题要求找出一个给定长度的区间内不断向右滑动中每个窗口的最小值维护一个双端队列deque并且是一个单调的双端队列队列存的是下标按题目要求单增还是单减这题是单增队头是当前队列的中的最小值对应的下标。那么怎么维护一个单调双端队列呢当当前元素比队尾元素小的时候如果直接放进去那么就违反了单增那这时就需要弹出队尾元素直到队尾元素比当前元素小。第二道题是石子区间dp问题要求将n堆石子合并的最小花费花费为每堆石子的个数和当只有一堆时不用操作就是最小花费了如果是两堆时把这两堆合并就是最小的了如果十三队的话就要看哪两堆和是最小的就先合并哪两堆但无论如何石子总数不会变那么最后合并为一堆时就一定是总的石子个数sum这是定的那如果有i堆呢不妨把i堆分成两堆然后每堆有继续分成两堆这样最后的答案就是从小问题开始了就很好解决了。

更多文章