Posts tagged with DP


OK,被逼得去学单调队列优化的dp 单调队列可以优化的DP有一大类就是多重背包。 因为本人是个DP弱菜,建议还是看其他人的博文…… 推荐博文 点这里 Coins 是 楼教主的男人八题中可以说是最简单的一道了。 简单说就是可行性多重背包,背包九讲中有关于可行性多重背包 ( O \left( VN \right) )算法的说明,虽然点到了单调队列优化,但也只是一笔带过。 题意: 有很多个硬币,各有价值a[i]与数量c[i]…

第一次听说用单调队列来优化DP…… 只能说见得少了…… 单调队列的限制很多,我已经几百年没用它了…… 但是有一些dp问题的子问题,的确可以转化成典型的单调队列问题,用单调队列优化之,可以将复杂度下降一个数量级。 题意: 有个人看穿了股市所有行情,现在他的本金无限,问可以赚多少钱。 这里的股市限制炒鸡多。 有限制: 最大所持股票数量 每天最大购买量 每条最大卖出量 当天购买的股票必须至少 n 天后才能卖出 最后给你看穿天数,每天收购与卖出价格。 思路: 可以说是单调队列优化DP的入门题了…… 设…

今天做的不太一样的状压,从去年的专题找的,看到学长并没有写是已经写过了么? 可能是因为跟图论相关的原因吧。 题意: 给你一个简单图,让你找出简单环的数量。 附 : 简单环就是没有重边和重点的环。 点数为 19 。 思路: 19个点,一般很容易想到状压和二维……根据数据猜算法? 事实上我是没有想到二维的 dp[ s ] [ p ] 表示 s 集合 p 为当前位置的边数 ,初始对每个状态…

前几天刚写了一道状压DP入门题,结果这次就遇到了,在比赛最后一点时间一眼看破,无奈只有想法,写不来…… 不过赛后尝试写的时候遇到了一个自己不会的问题,也就是说假如比赛的时候开了这道题,我也会一直卡着。 题意: 给你很多个行李的位置和起点的位置,要你把所有行李搬运到起点,一次只能搬一个或者两个,花费是距离,求最小花费。行李最多24个。 思路 状压dp,对于每一个状态,我们通过dp维护其最优。 因为这里的拿取行李是与顺序无关的,那么,我通过从小到大枚举状态,在保证我当前状态最优的前提下,由我当前状态拓展而来的状态只要通过比较就可以达到最优好暴力 所以我通过枚举,…

好题!!!! 这道题我整整想了一个晚上,怎么说呢,应该还是我从一开始就没想复杂,考虑得简单了,然后后面就写的很复杂了…… 其实我在写到一半的时候就突然想到我的状态转移方程是错的,然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰…… 题意: 一个90后都玩过的空间游戏吧,记得叫 是男人就下一百层 ,题意不是很好描述,可以自己去玩玩。 思路: 先说一下我最开始的想法,不想看的直接往下翻。 这道题我一看,诶,水题!我只要每次移动都保证当前层所花时间最少,类似记忆化搜索,一步一步推过去就能保证我的答案最优…… 首先这个思路的确是对的,…