[WC2020] 选课 (枚举+dp)

题面数据范围锅了导致枚举炸裂，写了正解却只有50分。。。。。。。

正确题面可以查看LOJ

记限制涉及到的不同的点个数为$P$

首先是不同的会被限制的个数$\leq 12$，所以应该直接枚举这些点的状态，枚举部分的复杂度是$O(2^P)$

(然后我枚举了$p$，实际$p\leq 66$啊啊啊啊啊啊)

对于没有被限制的点，可以优先预处理出每个类型的答案，注意到$L=T-\sum s_i\leq 40$，则可以每次只取出长度为$O(L)$ 的这一部分，类型之间合并为$O(ML^2)$的复杂度

或许比较难的点是在于每种类型内的合并，注意到$w\in\{1,2,3\}$

把每种$w$排序后，令$dp_i$为总权值为$i$的最小花费，同时记录最小花费时选取的三种$w$的个数，最优决策肯定是取最小的几个

每次转移，可以直接枚举选取的$w$，在排序好的数组上找到下一个最小花费

ps:事实证明，这个做法显然是假的，但是为什么就是没卡掉呢？正确的做法是先dp，w=1或2，再和3的暴力合并求出最大的$L$个值，这样的复杂度为$O(NL)$

ps2:后来测试，这个错误做法在值域只有200的情况下，随机情况下，整个值域中的错误率只有1/100~1/1000左右，而答案需要用到的部分又奇少，只有L个，于是乎，嘿嘿嘿嘿

如果用这种邪教写法，预处理的转移复杂度就是$O(N)$的

每次枚举之后，把被改变的几个类型答案重新计算，重新合并，这一部分复杂度就是$O(PL^2)$的

算上$2^P$次枚举，得到总复杂度是$O(N+2^PPL^2)$

Code