我开始做转化完还以为是给了我个 NP 问题，以为转化错了，没想到点开题解真是 NP 问题？
首先问题等价于相邻两个台子必须至少有一个激活，不妨连边，此时需要找一个最小权点覆盖，非常困难！怎么办？转化为补问题，求最大权独立集，折半搜索，那么预处理一个高维前缀和就可以合并了。
我开始做转化完还以为是给了我个 NP 问题，以为转化错了，没想到点开题解真是 NP 问题？
首先问题等价于相邻两个台子必须至少有一个激活，不妨连边，此时需要找一个最小权点覆盖，非常困难！怎么办？转化为补问题，求最大权独立集，折半搜索，那么预处理一个高维前缀和就可以合并了。