sigland

题解

/ 注册

全部文章 / 题解（共1篇）

C-奇奇怪怪的魔法阵折半枚举做法

出题人的题解很简洁，直接dp（S）表示S集合内有多少个独立集子集，然后考察S中随便一个元素i的情况，由之前状态转移过来，复杂度（2^n）但是事实上这道题可以通过折半枚举的方法优化到(n * 2^(n/2))。首先，按照题目中的说法一个一个求每个集合T内独立子集个数肯定不能找到更快的算法，因为此时...

C++ C++14 状态压缩前缀和动态规划

2021-10-20

2 536