【做题笔记】dp，但是国庆限定版

Day 1

方块消除

传送门

看到这个数据范围就可以猜测正解是 \(O(n^4)\) 的 dp，与这个差不多相符合的可以想到区间 dp。然后大胆猜测一下就是区间 dp，令 \(dp[i][j]\) 表示消除掉 \([i,j]\) 后的最大价值，这个显然可以从长度更短的区间转移过来。所以此题我们可以从区间 dp 的方向思考。

为什么不能用二维状态当普通区间 dp 做？ 假如按照普通区间 dp 做，可以造出任意一组需要三个合并消除之后的数据卡掉。这是因为这种 dp 具有后效性，我们不一定要全部消除 \([i,j]\) 这一段的方格，可以取一些保留下来，等到两边的区间都被消掉之后再将它与其他颜色相同的方格连续起来消掉。

所以就有一种很难想到的状态设计，令 \(dp[i][j][k]\) 表示消除 \([i,j]\) 这一段块的区间，但是 \(j\) 是和后面的 \(k\) 个颜色相同的方格（注意不是块）连起来一起消掉的。

为什么不能一个块一个块做？ 因为有可能最优解需要将一个块中的任意多个方格取出来先消掉，之后再消这个块中的其他块。

\(col[i]\) 表示块 \(i\) 的颜色，\(v[i]\) 表示块 \(i\) 的大小。设 \(sum[i]\) 表示在 \(i\) 后面有多少个与它颜色相同的方格。边界就是 \(dp[i][i][k]=(v[j]+k)^2(\;(k\le sum[i])\)。

在初始化的时候，为什么不加上由于要让后面 \(k\) 个块落到 \(j\) 旁边而消掉的区间的价值？ 所以我们补充一下状态的设计，这个状态仅考虑 \(k\) 个颜色相同的方格已经和 \(j\) 相连了它们的贡献 + \([i,j-1]\) 这一段的贡献，也就是不考虑让 \(k\) 个方格连续过来的贡献。

对于 \(dp[i][j][k]\) 它有两种可能的转移：

1. 单纯消掉 \([j,k]\)。
2. 找到 \([i,j]\) 中一个与 \(j\) 颜色相同的块 \(l\)，将它与 \(j\) 和 \(k\) 一起消掉。

对于转移 \(1\)，我们可以枚举 \(k\;(k\le sum[j])\)，\(dp[i][j][k]=dp[i][j-1][0]+(v[j]+k)^2\)

为什么 \(j-1\) 就不能接后面的东西了？ 如果 \(j-1\) 接的方格 \(x\) 在最后一个 \(k\) 的前面，那么要么 \(col[x]=col[k]=col[j]\) 导致 \(x\) 被保留下来了，但这显然不可能，因为 \(col[x]=col[j-1],col[x]=col[j]\) 但 \(col[j-1]\ne col[j]\)。所以 \(x\) 不会被保留下来，它早就会被消掉。如果 \(j-1\) 接的方格 \(x\) 在最后一个 \(k\) 的后面，考虑将 \([j,k]\) 消掉之后再消 \([j-1,x]\)，那么这实际上是一个更大区间的转移 \(2\)，我们这时候并不需要讨论。

对于转移 \(2\)，我们可以先枚举与 \(j\) 颜色相同的 \(k\)，再枚举后面要接的方格数 \(l\)，那么 \(dp[i][j][l]=max(dp[i][k][v_{[j]}+l]+dp[k+1][j-1][0])\)。也就是先将 \([k+1][j-1]\) 这一段区间消掉，让 \(k\) 和 \(j\) 连到一起，再将 \([i,k]\) 这一段且 \(k\) 是和后面 \(v[j]+l\) 个方格连在一起消掉的。

为什么 \(k,j\) 又可以当成一整块做了？ 注意状态是指消掉 \([i,j]\) 这一段块的整个区间的最大价值，那么无论是 \(k\) 还是 \(j\) 最后肯定都会被消掉。

最后的答案就是 \(dp[1][n][0]\)。

这道题是一种具有后效性的区间 dp，类似的题还有 它的双倍经验: 方块消除 Blocks ，祖玛。

Recovering BST

洛谷传送门

看到二叉搜索树，可以想到它有一个很好的性质：中序遍历单调不降。然后想到了 加分二叉树 这题，就可以考虑区间 dp 了（

考虑瞎套那道题，设 \(dp[i][j]\) 表示 \([i,j]\) 这一段是否能变成一颗树。但是此题与根节点还有关系，这样的状态并不能知道根节点是谁，所以设 \(dp[i][j][k]\) 表示 \([i,j]\) 这一段且以 \(k\) 为根节点是否能变成一棵树。

然后看一眼数据范围，\(700\times700\times700\)，空间直接爆炸。考虑优化。

一个常规的三维优化方式是将第三维变成只有几种取值的维度（参考类型：关路灯）。考虑是否有这种可爱的性质能让第三维变成只有很少的取值。

幸运的是，我们确实有这种性质！当 \([l,r]\) 这段区间变成一棵树的时候，当它成为下一个区间的右子树的时候，它的根节点是 \(l-1\)，当它成为下一个区间的左子树的时候，它的根节点是 \(r+1\)。这里只需要证明出两种情况中的任意一个，另外一个就能类似地推出来，所以这里只证明成为右子树的情况。

若 \([l,r]\) 这段为右子树，那么根据二叉搜索树的性质，它的根节点一定比这一段任意数小，也就是比 \(l\) 小，所以根节点取值范围是 \([1,l-1]\)。我们假设根节点是 \(l-x\;(1<x<l)\)，那么 \((l-x,l)\) 这一段也必定要放在 \(l-x\) 的右子树中，但现在右子树的形状已经确定为 \([l,r]\) 了。所以假设不成立，\(x=1\)。

为什么不能把 \([l,r]\) 这段区间中间的某个值提出来当根节点？ 这样的策略是可行的，但是我们发现在这种树上你要把 \(i/j\) 提出来也是可行的。我们只需要判断是否可行即可，而这种可行的话 \(i/j\) 为根节点也可行，所以没必要那么麻烦。

因此，我们设 \(dp[i][j][0/1]\) 表示 \([i,j]\) 这段区间且 \(i/j\) 为根节点是否能成为一颗树。状态转移的时候可以枚举断点 \(k\) 表示是从 \([i,k]\) 和 \([k+1,j]\) 这两棵树合并起来得到的。显然首先要满足 \(dp[i][k][0]=dp[k+1][j][1]=true\)。接着讨论是 \([i,k]\) 接到 \([k+1,j]\) 这颗树上还是 \([k+1,j]\) 接到 \([i,k]\) 这棵树上。根据二叉搜索树的大小关系，\(k+1\) 一定是最左边的左儿子，\(k\) 一定是最右边的右儿子，接过来的话一定是 \(i\) 变成 \(k+1\) 的左儿子或者 \(j\) 变成 \(k\) 的右儿子。判断一下这两种情况的 \(\gcd\) 是否为 \(1\) 即可。

为什么不能是 \(dp[i][k][1]\) 什么的转移过来？\(k\) 和 \(k+1\) 怎么你了？ 这实际上跟之前那个问题是一样的，只要其中一种可行，那么最后也可行，你硬要判断一下也可以过，但实测会慢一点。

最后输出的时候直接判断 \(dp[1][n][0]=true\) 或者 \(dp[1][n][1]=true\) 就行了。

为什么其他题解都说最后答案要枚举一下根节点？ 我不知道啊，但 实测 这样是可行的。并且理论上来说树的形态不会影响答案是否可行，那么最后也没必要枚举根节点了。也有可能是数据太弱吧/kk。

Dreamoon and Strings

洛谷传送门

这题难点大概是想到 dp 吧，毕竟看题面怎么都是一道字符串匹配题（。但发现用字符串算法好像没有什么很好的方法解决这道题（至少我不会），再加上可以想到 编辑距离 那题，想到这种删删减减字符串的题还可以用 dp 写，就大胆猜测一下是 dp。

设 \(dp[i][j]\) 表示 \(s\) 中的前 \(i\) 个删掉 \(j\) 个字符后包含的 \(p\) 的个数的最大值。首先无论如何都可以写出这样一个转移方程，\(dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])\)，意思就是当前这个字符要不要删。如果 \(s[i]=p[m]\)（\(m\) 为 \(p\) 的长度），那么就表示加上这一位后可能会贡献一个新的 \(p\)。但是要从哪一个状态转移过来呢？我们可以处理一下 \(f[i]\) 表示以 \(i\) 为结尾恰好产生一个子串的最大起点位置。这个可以 \(O(n^2)\) 预处理出来。那么这样就可以转移了，\(dp[i][j]=max(dp[f_{[i-1]}][j-(i-f_{[i]}+1-m)])\)。转移的过程中判断一下数组可能越位的情况就行，注意 \(i-f_{[i]}+1-m\ge0\)

答案输出显然是 \(dp[n][i](0\le i\le n)\)。