分类： DP

发布于

[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA

比赛时候：第一眼这不就DP吗，第二眼欸这东西怎么转移啊。。gg

当时迷了一直在想以AB和BA的数目为下标推，但是这样会有很多去重的问题。。。于是就没整出来，后来滚去推高数题了

看了叉姐的一句话题解大概懂了，推的时候直接用x和y的数目做下标，这样首先可以避免重复的问题。也就是设dp[i][j]为i个A，j个B时可用的前缀有多少种。这里面最重要的就是这个“可用的”怎么确定。这里的判断写出来很简单(i-j<=n&&j-i<=m).为什么是这样的呢？现在来考虑一个前缀，什么时候我们可以判断这个前缀一定不能作为最终答案中的某一个方案的前缀（也就是对最终答案没有任何贡献）？首先考虑凑AB，要用这个前缀的话，最终的结果是在他后面再补上(n+m-i)个A和(n+m-j)个B，注意这里的后面的排列并没有确定，也就是说我为了用到这个前缀（使答案+=它这种情况），可以尽力的去想办法摆布后面的A和B使得满足要求。那么有一个结论是在i-j>n的时候无论后面如何摆都满足不了要求：这个前缀至少可以配成j-1个AB或者BA，在加一个AB或者BA，然后如果i比j多了n个以上，那么意味着这多出来的i-j个A跟后面的配对只能配AB了，这样的话AB的总数就超过了n，由于AB和BA的总数确定的，这时候就一定不满足要求了；反之如果i-j<=n，则一定可以通过后面的调整来满足n个AB，m个BA的要求，可以自己试试看，只要注意到AB和BA的互换就行了。比如ABAB可以看出俩AB也可以看出一个AB一个BA（中间的）。。

然后dp边界是dp[i<=n][0]=1,dp[0][j<=m]=1，这个很好理解，全是A或者全是B就只有一种情况的。。。

这题还有点卡常，dp每次不要都memset，否则会tle 继续阅读“[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA”

发布于

[DP][字符串匹配][子序列] codeforces 1150 D Three Religions

vp了这一场，这个D题难到出现断层。。。C过了1k人的时候D没人过，太狠了

主要是能想到用dp搞字符串匹配的。。。div2里这样的人应该不多吧

但是这个题其实内涵里有诱导dp的思想：刚开始没有搞懂他这里的append是什么意思，后来才懂得他每次的+-操作都是在修改对应的religion的描述，这个描述是一个只有小写字母的先后顺序固定的字符串。。然后题目问的就是给定你一个字符串叫做word of universe，问3个religion能不能共存，其实意思就是能不能从这个word of universe分离出来三个subsequence，他们互不相交，又正好是3个religion的描述。

vp的时候毫无头绪，正解里的预处理表倒是想到了也写了但是没用上。确实没想到会是dp emmmm 。既然dp那一定有个数值型的对象吧，他这里就很妙的把问题转化为满足这三个subsequence共存的序列至少要多长了。。。当然给定的word of universe是确定的，这里其实可以认为后面还有无限长的字符串。。。但是长度大于n的时候我们认为没用了。。就输出NO就可以。不得不说确实是很精妙，legendary出的题确实厉害👍

具体地，设dp(n1,n2,n3)为region1满足前n1个字符，region2满足前n2个，region3满足前n3个这样的情况下所需要的在word of universe里的前缀至少有多长。有一个暴力的计算O(250^3)复杂度的，就是

\[
dp\left(n_{1}, n_{2}, n_{3}\right)=\min \left\{\begin{array}{ll}{Nst\left(dp\left(n_{1}-1, n_{2}, n_{3}\right)+1, \text{description}_{1}\left[n_{1}\right]\right)} & {\text { if } n_{1} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}-1, n_{3}\right)+1, \text{description}_{2}\left[n_{2}\right]\right)} & {\text { if } n_{2} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}, n_{3}-1\right)+1, \text { description }_{3}\left[n_{3}\right]\right)} & {\text { if } n_{3} \geq 1}\end{array}\right.
\]

继续阅读“[DP][字符串匹配][子序列] codeforces 1150 D Three Religions”

发布于

[DP][思维][×] codeforces 1183H Subsequences (hard version)

题目链接

题意：给定一个字符串S，长度为n≤100，然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里，每次操作的cost是(n-L)，然后问对于给定的k（k最大可取1e12），最少需要多少总cost才能使得set的元素个数达到k。难度2200分，有点虚高其实，不过还是不那么好想的。用先后顺序去重是关键idea。

做这种代码段但是考思维的小题还是挺有意思的。。。。

这题是mike出的，感觉挺经典那种。他有一个easy version是k≤100，这个要求的话就很松了，mike的题解直接用了一种及其暴力的方法：把每个subsequence当作一个点，相差一个字符的点之间连边建图，直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法，但是k≤100的时候很快就能搜到，只要及时跳出bfs就可以了。

这个H版本要求k最大可能是1e12，这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系，如果我们能求出来对应于某一长度j的unique子序列有多少个，那就可以解决这个问题了。这个就是一个引导方向，可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移，按照大问题转化为小问题的思想，dp[i][j]表示的以i结尾的unique子序列，那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列，数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息，这个一定是某些dp[pos][j-1]之和，但是有一种情况的是不同的pos对应的子串可能一样，所以这个题目最精彩的部分就来了，每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏，如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少，即不漏；第二这个就避免了重复计算的现象，不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为

\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]

至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];
继续阅读“[DP][思维][×] codeforces 1183H Subsequences (hard version)”

发布于

[动态规划][状压DP][剪枝搜索] XDOJ 1420 2019西电acm校赛网络赛J题 垒箱子

题目链接

这次学校网络赛还是挺不错的，有3道题（F I J）都是值得一做的emm，J题胡乱暴力+dp拿了个一血，I题胡乱暴力也过了

当然由于我FFT/NTT&斯特林数学的不行所以F题并不会做，虽然推出来公式和dalao一样但是没法把复杂度降下去，等到学会了应该会放个F的题解

J题吧，跟UVa 437 The Tower of Babylon很像，当然只是看上去很像，UVa 437的限制是每种箱子必须叠在比他严格小的另一个上，然后箱子无限用，XDOJ 1420 是叠在长宽大于等于该箱子的另一个箱子上，但是每种箱子只能用一次。
如果箱子的数量少一点的话，其实完全可以直接完全状态压缩动态规划，但是这题数量是30，压缩成二进制的话2^30肯定会超时，所以需要一点操作。。

首先先全部暴搜，dfs(x,S)表示当前以箱子x号为最底部箱子，之前已经用过的也就是还在x更底下的箱子情况为S（S是一个十进制数，展开成01二进制串表示30个箱子是否被使用过）所能达到的最高的高度，每次都打一遍结果，很快可以发现，当取到某一个箱子之后，在某些情况下他后面的搜索路径就是固定的。

就比如说 某次搜到了箱子3，然后他之后的搜索路径就只能放箱子6和7，然后把每次搜索路径都打出来就会发现，其实之后的每次搜到3都会是走6和7，除非6和7之前已经被用过了也就是说6或7变成了3底下的箱子，这时候后面的路径会发生一些变化，因为每个箱子只能用一次。（这里本该举一组样例但我实在找不到当时画的样例了emm）

然后到这里就可以想一下是不是可以用这个特性对dfs(x,S)进行剪枝和记忆化搜索，首先把S的定义反转，让S这个二进制数表示尚未使用过的箱子”的情况，比如00101表示1号和3号箱子还没有被用过，245号箱子已经被用过了。这样的话，每次dfs的时候可以记录下来一个dp(x,TS)的记忆化结果，其中TS是S和“理论上可以放到x上的所有箱子的集合”KS相与的结果，这里后者可以n^2复杂度枚举预处理，我的代码里是存储到ky[x]的数组里。这样的话，每次dfs就是先把TS求出来，然后判断(x,TS)这个对有没有在之前被搜索过，如果有的话就直接返回结果，这里的这个结果可以用一个map<pair<int,int>, int> 来保存，如果没有出现过的话的话就直接暴搜，这样的话每种箱子作为底的每种情况只会被搜到一次，就等于提前把绝不可能走到的箱子和已经走过的路径都剪掉了。把所有的状况想象成图的话，每个箱子三种形态那就是有90个节点，每个结点出发能走的最长的路径最多30个，如果能保证每种情况只走一次其实是相当快的（主要是我并不会严格证明复杂度emmm）

继续阅读“[动态规划][状压DP][剪枝搜索] XDOJ 1420 2019西电acm校赛网络赛J题 垒箱子”

发布于

[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps

题目链接

思路比较简单但是很经典的一题，最近一直在补数学。。

用dp(u)表示以节点u为根的种类数，则由基本的组合数学可以得出\[dp(u)=(\frac{(n-1)!}{\prod size(v)})*\prod dp(v),\ u\ is\ v’s\ parent\] 其中\[size(v)\]是以v为根的子树的大小。然后由于这里模值是任取的，所以不能用求逆元的方式来做，否则的话也太简单了。

考虑进一步化简这个式子，把\[dp(v)\] 们展开（脑海中展开）可以发现对于每个节点来说，他以 \[(size(v)-1)!\]的形式出现在分子上一次，以\[size(v)!\]的形式出现在分母上一次，所以最终把所有节点（不仅仅是root的直接儿子）全部代进去就可以得到\[dp(root)=(\frac{(n-1)!}{\prod_{v=2}^{v=n} size(v)})\]
继续阅读“[组合数学][大组合数取模][TreeDp] UVA 1436 Counting heaps”

发布于

[状压DP][枚举子集] UVALive 4794 Sharing Chocolate

题目链接

简单分析易知如果Yes的话整块巧克力一定是从最初的一大块不断地分成矩形来实现的，而一个矩形分成两个小矩形的方法只有两种，横着分或者竖着分，这样的话就可以枚举断点分割，大问题转化为小问题递归解决。然后总共的小块数量最多15，很明显可以用二进制表示获得的块的状态。但是直接定义类似\[dp(r,c,S)\]这样的状态会造成\[O((x+y)xy2^n)\]的复杂度，基本上不能通过这个题（其实做了极致的优化的话时间上应该可以做到但是空间复杂度会超过2GB）。然后考虑状态的进一步化简，可以发现实际上如果确定了S，则可以通过r和c中的一个计算出另一个（或者发现根本不存在这样的数），由此只需要考虑\[dp(r,S)\]即可，其中r是原状态r，c中较小的那一个。另外，枚举分割点时间是并不优秀，因为还得检查当前集合是否支持这样的分割，不如直接枚举所有的子集分割情况，然后用这个来算出分割后的子函数的r和c。按照计算矩阵链乘的方式来做复杂度分析可以算出时间复杂度\[O(x3^n)\]。直接记忆化搜索的话，会比这个上限要小得多。
继续阅读“[状压DP][枚举子集] UVALive 4794 Sharing Chocolate”

发布于

[AC自动机][Trie图][期望DP][高斯消元] Generator UVALive 3490

又是一个Trie图上找递推关系的题~只不过这次是单字符串做一个Trie图（这样的话用扩展kmp也可以8

把样例研究一下再结合Trie图基本就能确定出等式关系了，设dp[i]为

现在在Trie图上的节点i，还需要走多少步（期望意义下）才能凑出给定的字符串

容易知道当走到尽头的时候dp[n]=0;其他的项地推关系可以表示为dp[u]=1+\sum i/n*dp[v] ,其中v是u走向的下一个节点。

以样例n=2,s=”ABA”为例，Tried图和方程组如下

解这个方程组可得dp[0]=5,就是我们要的结果了。

具体代码实现的时候，直接对每个结点都把转移记录下来，然后用高斯消元解方程即可。注意应该把n乘到等式左边，然后用整数的高斯消元，不然会有误差wa。
继续阅读“[AC自动机][Trie图][期望DP][高斯消元] Generator UVALive 3490”

发布于

[AC自动机][状态压缩DP][DFS]

题目链接： Password Suspects

这题让我回想起了某现场赛被某大佬支配的恐惧

感觉是dp，而且这个子串的数据量一看就是状压，然后在推转移方程的时候死活推不出来一个不交叉的。可耻的搜了题解，看到大佬们的标题：AC自动机+DP
我就

~~其实是常见的一种操作只是我太久没做过字符串的题目了~~
在思考递推方程的时候就一直在纠结前缀与后缀重合的这种情况怎么表示状态，然后忽然意识到ac自动机（更确切的说是Trie图）就是可以唯一的确定一个匹配状态的数据结构！这种题一般都是给定一些字串，然后给出一些约束条件，比如要求

  • 匹配所有字串，这种就是本题类型的，往往需要状压
  • 不能匹配任一字串，即匹配走过的路径上不能有任何一个危险节点
  • 满足某些条件的字串
  • 等等等等（我还没来得及总结那么多

继续阅读“[AC自动机][状态压缩DP][DFS]”

发布于

[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II

去年校赛的时候感觉此题难的一批，，，昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟。。。Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了。

这个题的思想就是：把每一列3*1的小方格当成一个“珠子”，把他可能的8种情况当成“颜色”，然后这些颜色同时也代表状态，类似于poj2888的颜色相邻限制，这里的状态之间“能不能相邻”其实就是在状压dp里“能不能转移”的限制，不同状态之间的转移图如下（来自matrix67的那篇文章

继续阅读“[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II”

发布于

[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka

紫书DP课后题最后一题了，也算是把这一部分做完了吧。
这个题，在uva上的数据太水了，导致很多网上的题解代码是错误的。在gym10128H这里会wa。这些题解大多是用一个简单的贪心策略处理分段，然后用区间dp处理分出来的段落。但是实际上分段也需要用一个dp，比如数据 1 2 4 3 1 2，用简单的贪心分段就会把4 3分到前面那一段，这样的出来结果是5（当把1 2 放进4 3里的时候4和3都要打开），但是如果把4 3分到后面的1 2里答案是4，是更优的解。

先讲简单的部分：分好段之后的区间dp。这个就是普通的区间dp $$dp(l,r)=min(dp(l,i)+dp(i+1,r)+cost(l,i,i+1,r)),i\in[l,r)$$其中 \[dp(l,r)\]表示
[l,r]之间的套娃组装成1个所需要的最小花费, 继续阅读“[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka”