HDU 4899 Hero meet devil

By NodeKey in ACM on

训练赛的DP套DP，关于DP套DP，以前记得好像做过一道。题目本身十分巧妙，但貌似不是很多。可能不是很好出题吧。 所谓DP套DP，就是我DP所需的状态也需要额外的DP求出来。简单说，就是我需要DP两次，在第一次的DP结果上再DP一次。 题意： 给你一个DNA序列，再给你一个固定长度，问你在这个长度下的所有序列中，与给定的DNA序列的LCS分别为( [0,len(DNA)] )的序列数量。 思路： 因为数据很小，我们可以考虑用状压做。 对于当前长度的一个最优状态，如果增加一个字符，它的下一个状态就需要加上当前状态的序列数量。 这是一个非常常见的计数DP。 但是已知当前状态，无法直接得出下一个状态，而这个就是我们需要嵌套在内的DP了。 我们枚举每一个状态，在枚举每一个字符，使其插入当前状态，再转移它的LCS，最后再统计一下就可以了。 而统计方法是如果当前位置的LCS与前一位置的LCS不同，则说明这个位置与LCS的DNA序列匹配。 虽然我说的很简洁，但是我当时也是想了好长时间…… AC Code #include usi…

HDU 4628 Pieces

By NodeKey in ACM on

CLS的状压DP系列…… 然而实际上也算是一道简单题，但是我并没有立刻写出来。 不知道为什么，每次我尝试这用已知最优状态去推其他状态都是错的…… 然而用当前状态之前的状态来推当前状态却是对的。 顺便学习了一个，二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state ) 学了这么久状压居然连这个都知道真是醉了…… 题意： 给你一个字符串，每次只能取走一个回文串，问最少取几次。 思路： 先预处理出所有状态是否为回文串，并使得 这个状态取值为 1 。 枚举每个状态，再枚举它的所有子集。 状态转移方程 为 dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s] ) AC Code #include #define each(i, n) for…

CodeForces 842 C Ilya And The Tree

By NodeKey in ACM on

树上的选择性DP…… 不是很懂其他人的做法，偶然间看到有人用ruby A了，我也就用ruby敲了一蛤 速度有点玄…… 题意： 给你一棵树，每个节点都有权值，要你求每个节点到根节点所形成的树链 gcd。 其中每条树链都可以选择一个节点使得权值变为 0 。 思路： 感觉这就是裸题…… 只不过就是把数组改成树上了而已。 用一个栈或者队列去遍历这棵树，对于每个节点是否变0都考虑一下就好了…… AC Code #!/usr/bin/env ruby # encoding: utf-8 n = gets.to_i a = gets.split.map(&:to_i) g = Array.new(n) {[]} (n-1).times do u, v = gets.split.map(&:to_i)…

HDU 6143 Killer Names

By NodeKey in ACM on

昨天的多校应该是团队合作最失败的一次…… 一开始过题人数最多的那道题许颂嘉没去想，只能我自己上了，第一直觉就是DP，但这个状态转移真的想了我好久好久，但想出来后又觉得是非常显然的…… 后来不知道什么时候许学姐来想这题了，估计是急了，也没跟我说，然后就是两个人单独想题的局面，还瞒着我敲了一发容斥……是的，一个队里两个人同时用两种算法在想同一题。这是团队赛最忌讳的。 也可以说是最愚蠢的。 之后敲完之后雨情学姐又给了我一个错误数据，先是打乱我的思路，然后debug了将近一个小时，发现数据错误之后，把最开始的代码交了一发就秒了…… 不想多说什么，这场明明还有一道很简单的细心题，当时急了，没发现重点。和一道几乎是AC自动机入门题的题，没看。 我特么 心如刀割。 题意： 给你一个长度( n\和字符数量( m)，让你组成两个字符串，两个字符串两两不能有统一字符。 思路： 标程是容斥，我不会，这题提供DP解法。 令( dp[ len ] [ num ] ) 表示长度为( len ) 的字符串并且有( num )个字符的数量。 那么我现在只考虑一个字符串，它的长度固…

BZOJ 4197 寿司晚宴

By NodeKey in ACM on

上一场多校一道状压DP的原题。 那我肯定是去做原题啦。 多校的时候我还觉得这肯定是许学姐的锅，没想到居然能转化成状压。 题意： 中文题面，给你( [ 2, n ] ) 这几个数，要你各找两组数字，两组数字之间两两互质。 ( n) 最大为500，问组合数量。 思路： 考虑数据 ( n) 非常小，在 ( \sqrt 500 )以内的质数只有8个，而大于( \sqrt 500 )的大元素只可能为一个，那么我们把相同的大元素放在一起处理，开一个二维数组表示这个大元素在两组中的哪一组，而对于小元素，可以用状态压缩来表示两组数字各自包含那几个质数。最后累加的时候让两个状态不重叠即可。 代码中 ( dp [ k ] [ a ] [ b ] [ c ] ) 表示 前( k)个元素中 第一组数包含的小质数状态为( a) ，第二组数包含的小质数状态为( b) ，大质数为在第一组( 0) ，或者在第二组( 1)…

区间DP入门 —— 三类经典问题

By NodeKey in ACM on

例行废话 大概是前天试着去入门区间DP，中间穿插了很多其他题目，今天勉强入门并多写了几题。 又被goubi带鱼笑了，shit！ 有些时候我自己也会觉得写一些入门的东西会有点浪费时间…… 但我又想了想，应该说是每个人写博文的目的不同吧。 像我这种小网站，我也不渴求能帮到多少人，只是记录一下自己的成长罢了。 三类经典问题 区间DP被goubi带鱼说是最简单的DP，因为它是有套路可循的。 这个套路就是用小区间推出大区间。是的，这个套路就是这么简单，其他的还是考虑状态与个人思维了。 而小区间推出大区间的方法自然是按照区间长度不断向后DP，每次将所有长度相同的区间长度推出。 一般来说，把这个这个思维熟练了，再学一个四边形优化，区间DP就可以毕业了。goubi带鱼如是说 而关于三类经典问题，大多数区间DP都可以通过转换得到这三类基础模型。当然我也是听别人说啦，我也才刚入门啊 石子归并 传送门 题意： 给你一排石子，你只能将相邻的石子合成一堆，花费为两堆石子的重量和。问如何合并，花费最小。 思路： 如果去掉相邻石子才能合并的限制，那就是一个…

状压DP 再入门 ！！！

By NodeKey in ACM on

昨天写状压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 )时，就表示上下状态的玉米不会相邻，这两行是满足题意的，所以只要将当前状态的数量加到下一行的状态中。…

POJ 1742 Coins

By NodeKey in ACM on

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 ，若…