简单分析易知如果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”