[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