分类： 优化DP

题目链接

这次学校网络赛还是挺不错的，有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题 垒箱子”