題目鏈接:uva 11825
題意:
你是一個黑客,侵入了n台計算機(每台計算機有相同的n種服務),對每台計算機,你可以選擇終止一項服務,則他與其相鄰的這項服務都終止。你的目標是讓更多的服務癱瘓(沒有計算機有該項服務)。
思路:(見大白70頁,我的方程與大白不同)
把n個集合P1、P2、Pn分成盡量多的組,使得每組中所有集合的並集等於全集,這裡的集合Pi是計算機i及其相鄰計算機的集合,用cover[i]表示若干Pi的集合S中所有集合的並集,dp[s]表示子集s最多可以分成多少組,則
如果cover[s]=all,那麼dp[s]至少為1.
dp[s]=max(dp[s],dp[s0]+dp[s^s0]); (兩個子集的和)
代碼:
#include#include #include #define N 16 using namespace std; int n, m, x, dp[1<