I Wanna be the Team Leader - 洛谷
-
差一点就想到了/ll
-
遇到困难？排序肯定不会变差！
-
性质：每个项目分配的程序员肯定是一段（显然）
-
\(m\) 很小？考虑设 \(dp_{i,S}\) 表示考虑前 \(i\) 个人选项目集合为 \(S\) 能否可行
-
转移显然，复杂度 \(O(n 2^m)\)
-
这里我忘记了我设的 \(dp\) 值是能否可行，就以为不能继续优化了，
wssb -
因为 \(dp\) 值存的 \(01\)，因此优化成 \(dp_S\) 表示选项目集合 \(S\) 时右端点最靠左是哪里
-
转移时要预处理 \(g_{i,j}\) 表示选取第 \(i\) 个项目从 \(j\) 开始转移到哪。可以双指针预处理
-
最终复杂度 \(O(nm + m2^m)\)
-
总结：\(dp\) \(01\) 问题可以优化掉一维来优化复杂度