昨天写状压DP被煞笔天海和死肥宅带鱼嘲笑了 Damn！ 然而事实也是一些状压DP的经典问题我还不会…… 更烦人的是今天的多校是DP专场，AC自动机+DP 这个倒是常见的套路 树形DP ，反背包DP，树上匹配+DP，各种姿势的DP…… 老实说，我的DP是很弱的……连背包问题上的我个人觉得都不是很熟练…… 这里写一下状压DP入门的三道题，三道题其实差不了多少，但在难度上基本上是循序渐进的。 POJ 3254 Corn Fields 题意： 给你一个矩阵，让你种一些玉米，要求只能在给定的格子上种，并且相邻的格子不能同时存在玉米。 问方案数。 思路： 首先在输入的时候记录一下每一行不可种植的格子，将它压缩为二进制。 再是筛选出在同一行满足条件的所有状态，因为不能存在相邻格子，也就是 ( i & ( i << 1 ) = 0 ) 枚举每一行满足条件的所有状态，进而枚举下一行满足条件的所有状态，当 ( state[i] & state[j] ==0 )时，就表示上下状态的玉米不会相邻，这两行是满足题意的，所以只要将当前状态的数量加到下一行的状态中。…
OK，被逼得去学单调队列优化的dp 单调队列可以优化的DP有一大类就是多重背包。 因为本人是个DP弱菜，建议还是看其他人的博文…… 推荐博文 点这里 Coins 是 楼教主的男人八题中可以说是最简单的一道了。 简单说就是可行性多重背包，背包九讲中有关于可行性多重背包 ( O \left( VN \right) )算法的说明，虽然点到了单调队列优化，但也只是一笔带过。 题意： 有很多个硬币，各有价值a[i]与数量c[i]，问你能构成的价值种数有多少。 思路： 这里简单说一下我对单调队列优化的理解吧 其实这里根本算不上单调队列，只能说是队列，其实就是问题被简化了。 对于每一个价值，都可以被转化成 ( d + n \times a[i] ) ， 其中 ( d \in \left[ 0 , a[i] \right) ) 简单说就同余关系啦 那么对于一个价值 k ，若…
第一次听说用单调队列来优化DP…… 只能说见得少了…… 单调队列的限制很多，我已经几百年没用它了…… 但是有一些dp问题的子问题，的确可以转化成典型的单调队列问题，用单调队列优化之，可以将复杂度下降一个数量级。 题意： 有个人看穿了股市所有行情，现在他的本金无限，问可以赚多少钱。 这里的股市限制炒鸡多。 有限制： 1. 最大所持股票数量 2. 每天最大购买量 3. 每条最大卖出量 4. 当天购买的股票必须至少 n 天后才能卖出 最后给你看穿天数，每天收购与卖出价格。 思路： 可以说是单调队列优化DP的入门题了…… 设 dp [ i ][ j ] 为第 i 天持有 j 股的收益。 则状态转移的规则就是 取 1. 不买不卖 dp [ i – 1][ j ] 2. 买入 限制下的 股数 的最收益…
最小割建图好题！！
昨天比赛的最小割，当时没看出来，实际上需要建图转化一下，这道题非常显然！！！
比赛后不想看题解，问了一下Yasola，指点了一下马上懂了！！
题意：
有n×m的地图，地图上最多有6个国家，现在K国要修长城，来防御敌对国家，6个国家中除了K国和一个敌对国家，其余国家都是友好国家，想要进供从而使得自己在长城防御范围内。建立长城的每一个花费都已经给出。
问最小花费。
思路：
将地图以外的地方视为敌对，将一个地图上的格子与其上下左右相连。
对于一个长城，实际上就是将K过与友好国家 与 敌对国家割开的最小割。
又因为点数和边数都很少，最多通过枚举 2^5 枚举将友好国家包围的情况，每次求一下最小割即可。
AC Code
#include
算法详解 花了一点小时间入门了 kosaraju 算法。 记得之前在一篇博文中提到过，ACM中求强联通分量的常见算法有三种： 1. 暴力 2. Tarjan 3. Kosaraju 其中暴力和 Kosaraju 算法在求强联通分量的同时，可以直接输出可行解，而Tarjan则需要通过额外的拓扑排序来得出可行解。 简单说一下 Kosaraju 的基本思路： Kosaraju算法主要通过一个非常显然的性质来求强联通分量的。 对于一个强联通分量，将它的所有边反向，那么它依然是一个强联通分量。 因此，我们通过两边dfs，第一遍dfs求出整张图的拓扑序，第二遍dfs按照拓扑序通过反向边进行拓展。 这个地方就非常巧妙。因为在按照拓扑序遍历的过程中，对于一个点，如果它是一个强联通分量的一个点，那么除开原先遍历标记过点，必然会存在拓扑序在该点之后但仍然指向该点的一个点。 好难表达，yy很容易 题解 题意： 有一群牛，给你很多个关系，一对关系 a -> b 表示 a 认为 b 是肥宅，问被所有牛公认为肥宅的牛有几头。…
第一次刷到HDU第一名，趁现在没人比我高，截图来一发！！！！ 对于这道题，我只想说一个字 妙！！！！ 题意： 给你四个点，(1,2),(2,3),(3,4),(4,1)之间都有一条无向路径，让你从 2 号点出发，最后回到2号点，同时使得走过的距离大于等于 k ，并且 最小。 k很大，最大达到 1e18 ，四条路的范围不大于 3e4 。 思路： 这道题真的是太妙了！！！ 说一下我比赛前后的思路，这里我称 从 起点 2 回到 2的回路为 E 回路。 先说一下我比赛的思路： 一开始我的思路是这样的，首先不考虑单纯的往返，那么E回路就有7种情况。 那么我考虑复杂度的话最多的就是4点成环且只有4条边的情况，对于这条已有的E回路，我们可以在任意一条路径走来回走，使得路径长度增大。 那么我们就可以将问题转化成为…
今天多校的第一锅…… 这套题真是神奇，明明都是Claris出的，涉及图论的居然有4道…… 而且就这道题来说，有一个卡点真的是很让人觉得奇妙。 题意： 给你一个两边点数相同的二分图，左边的点都会连接右边两个不同的点。 求 每一个完美匹配的边权积 的和。 思路： 真特么神题…… 一开始我看到这题，潜意识的想到网络流，看到点数这么多认定不可能是网络流。又通过每个左边集合的点都有两个选择，互相矛盾想到2-sat，但需要输出所有可行解又十分困难。于是我猜测，最多只有两个方案。但是被队友反驳了……最后就没出…… 其实基本思路已经对了。的确是求2-sat的所有可行解。但是会有一些优化的地方。 一开始，我们对于右侧的点，如果他的入度为 1 ，那么我们的选择是确定的。用这个方式对整张图进行拓扑排序。最后获得左右两侧都有 m 个点，并且右侧的点的入度都大于等于 2 。 因为此时左侧只有 m 个点了 ，那么左侧的出度和也就是右侧的入度和 就是 2m ，因此右侧的每个点的入度都为 2。 对于这样的图，图中的每一个强联通分量内，他的可行方案的确是两个，自行yy即可。…
今天在回寝室之前A的最后一题，是前年多校的一道最小树形图。
老实说，一开始看到这题第一想法，是将所有终点练到超级汇点，然后跑最短路。冷静了一下发现完全搭不上边……
比如说当你学到了某一个课程的level 5 ，那么该课程的level 4 ，level 3都是无消耗可达的。
是的，说到这，学过最小树形图的十有八九都会有思路，将同一课程高level指向低level，消耗为 0 。建立超级汇点连接每一个课程，再将培训班建边，跑一跑朱刘即可。
题意：
小明有n个课程，每个课程有个理想的level，他想通过补课来达到这些level。补课形式是你在a课程达到某一个level，那你补完之后就会在b课程直接达到 另一个level，花费给定。
求最小花费。
思路：
见上。
AC Code
#include