Posts

动态规划2-背包DP 装箱问题 有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入描述：一个整数v，表示箱子容量；一个整数n，表示有n个物品；接下来n个整数，分别表示这n 个物品的各自体积 输出描述：一个整数，表示箱子剩余空间。 样例输入: 24 6 ​ 8 3 12 7 9 7 样例输出：0

笔记 最优子结构：子结构最优，全局一定最优 无后效性：各个决策部分单独存在，不会相互影响

终于有一次能在考场上打出正解的模拟赛

题面 相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

思路：单调队列 以求最小值为例 在读取每一个数 ai 的过程中，判断队尾的数是否大于ai,如果大于则证明队尾的数已经没有意义了，因为*它已经不可能成为现在及以后所有窗口内的最小值*，不妨弹出，重复以上操作，直到ai小于队尾的数，再把ai放到队尾 当现在的长度已经达到窗口的长度时，每一次都会输出最小值，因为队列是单调递减的，第一个数一定是现在窗口内最小的数，直接输出 在队尾添加的过程中，*要始终保证队列里的数都在窗口内*，当区间长度大于窗口长度时，要从队首弹出 自己遇到的坑 *队列内存储的是这个数的位置，不是这个数的大小*，大小通过数组类似映射表示