第一次听说用单调队列来优化DP…… 只能说见得少了…… 单调队列的限制很多，我已经几百年没用它了…… 但是有一些dp问题的子问题，的确可以转化成典型的单调队列问题，用单调队列优化之，可以将复杂度下降一个数量级。 题意： 有个人看穿了股市所有行情，现在他的本金无限，问可以赚多少钱。 这里的股市限制炒鸡多。 有限制： 1. 最大所持股票数量 2. 每天最大购买量 3. 每条最大卖出量 4. 当天购买的股票必须至少 n 天后才能卖出 最后给你看穿天数，每天收购与卖出价格。 思路： 可以说是单调队列优化DP的入门题了…… 设 dp [ i ][ j ] 为第 i 天持有 j 股的收益。 则状态转移的规则就是 取 1. 不买不卖 dp [ i – 1][ j ] 2. 买入 限制下的 股数 的最收益…
今天做的不太一样的状压，从去年的专题找的，看到学长并没有写是已经写过了么？ 可能是因为跟图论相关的原因吧。 题意： 给你一个简单图，让你找出简单环的数量。 附 ： 简单环就是没有重边和重点的环。 点数为 19 。 思路： 19个点，一般很容易想到状压和二维……根据数据猜算法？ 事实上我是没有想到二维的 dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ，初始对每个状态 dp [ 1<< i ][ i ] 设置为 1 对于每一个状态，固定的从最小的一位 1 作为起点，从这个起点开始扩散，如果能回到这个起点，就进行计数。 因为对于一个环，枚举起点和终点的话，会存在起点到终点，和以终点为起点的情况。 比如说 1-> 2 -> 3 ->1 和…
前几天刚写了一道状压DP入门题，结果这次就遇到了，在比赛最后一点时间一眼看破，无奈只有想法，写不来……
不过赛后尝试写的时候遇到了一个自己不会的问题，也就是说假如比赛的时候开了这道题，我也会一直卡着。
题意：
给你很多个行李的位置和起点的位置，要你把所有行李搬运到起点，一次只能搬一个或者两个，花费是距离，求最小花费。行李最多24个。
思路
状压dp，对于每一个状态，我们通过dp维护其最优。
因为这里的拿取行李是与顺序无关的，那么，我通过从小到大枚举状态，在保证我当前状态最优的前提下，由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力
所以我通过枚举，找到第一个它能够搬运的行李，每次都拓展这个状态即可。
AC Code
#include
好题！！！！ 这道题我整整想了一个晚上，怎么说呢，应该还是我从一开始就没想复杂，考虑得简单了，然后后面就写的很复杂了…… 其实我在写到一半的时候就突然想到我的状态转移方程是错的，然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰…… 题意： 一个90后都玩过的空间游戏吧，记得叫 是男人就下一百层 ，题意不是很好描述，可以自己去玩玩。 思路： 先说一下我最开始的想法，不想看的直接往下翻。 这道题我一看，诶，水题！我只要每次移动都保证当前层所花时间最少，类似记忆化搜索，一步一步推过去就能保证我的答案最优…… 首先这个思路的确是对的，但却忽略了一个细节，从我以前走过的层到我当前层，有个位置上的关系。 就是说当我每次得到当前层时间最短的时候，我必须把落下的相应位置给确定下来，否则，若存在重复的最优时间，当前下落位置不同，会影响之后的时间。这是显然的。 而我要想补救我的思路，那我必须记录所有的位置，虽然这个位置数量不会超过2，但这实现起来就很烦。 正解： 其实正解是很简单的，我只要反向思考就可以了。就是记录当前层到底层的最短时间。考虑当前层到中…
虽然可以算得上是道水题，但作为我第一道状压DP，还是把它写入我的博客。
觉得这道题作为入门题是极好的，比网上说的什么矩阵的好理解的多！！
因为几乎只涉及了状压
特别想感慨一句，dp真的是个优美的暴力啊……
题意：
有几门课的作业，分别给出截止时间，完成所需时间，没拖一天扣一分，问最少扣多少分，并输出写作业顺序。
思路：
总的思路是对于每一个状态，都进行课程的枚举，并计算花费时间，拖作业时间，从而进行状态转移，每次状态转移都使拖作业的时间最小即可。
不是暴力？？但是真的很优美！
课程数很小，只有15门，因此状压无压力。
AC Code
#include
老实说有点崩溃，一场训练赛，3道dp都没出，两道还是全世界都A了 毫无疑问，又落后一截…… 实在不明白他们的dp为什么这么6…… 题意： 给你一个序列 ( a_1 a_2 a_3 a_4 …… a_n ) 要你求相邻两个元素在矩阵中的数值和。 矩阵已给定，但是如果序列元素为负数，则可以为任意元素。 思路： 渐渐觉得dp就是暴力…… 四种情况 ary[i-1] < 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i – 1][k] + mat[k][j])ary[i-1] < 0 && ary[i]…
坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑！！！！！！！！！
套着二分图外套的DP题！！！！
连续栽在这个类型的题上两次！！！！！！！！
一次是上次选拔赛的时候，那时候有两道题，一道是很明显的二分图，另一道稍微隐蔽一点，但是全都栽了，我以为，建了图我就是赢家，特么的根本建不出来！！！
上次就像写一篇来阐述一下某些二分图匹配的DP解法，无奈太懒了，结果今天就又栽在这里了……
题意：
给你一张二分图，要求点权相同的点才能相互匹配，而且每个匹配有且必须要有一个权值不同的匹配与其交叉，问最大匹配数量。
思路：
很容易想去匈牙利了有木有！！！但事实却是，dp求解。 思路如下：
假设我们要考虑的状态是第一行n位置，第二行m位置，且已知之前的所有最佳状态。考虑把，n，m交叉的匹配加入到匹配集合中。那么 如果两点的权值相同则不符合要求，否则，分别向前查找各自的匹配，再与这个状态之前的状态转移即可。
如果你还不懂，那你看一遍代码肯定能懂。
AC Code
#include
菜笔只会 O( n ^ 2 ) 的 LIS 的求法，现在补上……其实也非常好理解
这道题我记得很久很久之前就做过原题了，只要求两遍 LIS 即可，但是本来今天就OJ就很卡，好不容易交了两发，本以为两发都 WA 了 ，结果一发 waiting ，一发RE……
这里补上代码以备模板之需
题意：
找出左边递增右边递减，长度相同的子序列。
思路：
两遍LIS，同位置求最小。
#include