-
无意看一眼标签是 \(dp\) 就一直朝树形状压 \(dp\) 的方向想了一年，发现不是树形 \(dp\)
-
设 \(dp_S\) 为完成集合 \(S\) 内的限制所需要的最少边数
-
把每一对顶点的路径上每条边的值都状压，表示添加这条边可以实现的限制有哪些，记为 \(b_i\)
-
因此有：
-
\[dp_S = min\{ dp_{S-b_i} + 1 \} \]
-
但是还没有结束，因为直接这么做是 \(O(nk + 2^kn)\) 的
-
这里需要一个重要结论：不同种类的 \(b_i\) 只有 \(O(k)\) 个
-
考虑把一个 \(L\) 型的限制对拆成两个 \(I\) 型的，种类数一定不会减少
-
而对于每一个加入的 \(L\) 性，显然最多增加两种类型
-
因此最终种类数是 \(O(k)\)
-
因此我们只需要把 \(b_i\) 去重即可做到 \(O(nk + 2^kk)\)
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。