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\) 问题可以优化掉一维来优化复杂度