題目鏈接Click Here

【題目描述】

假如你是一個黑客，侵入了一個有著\(n\)臺計算機（編號為\(1.2.3....n\)）的網絡。一共有\(n\)種服務，每臺計算機都運行著所有服務。對于每臺計算機，你都可以選擇一項服務，終止這臺計算機和所有與它相鄰計算機的該項服務（如果其中一些服務已經停止，那他們繼續保持停止狀態）。你的目標是讓盡量多的服務完全癱瘓(即：沒有任何計算及運行著該服務)

【輸入格式】

輸入包含多組數據，每組數據的第一行為整數\(n(1<=n<=16)\):以下\(n\)行每行描述一臺計算機相鄰的計算機，其中第一個數\(m\)為相鄰計算機個數，接下來的\(m\)個整數為這些計算機的編號。輸入結束標志\(n=0\)。

【輸出格式】

對于每組數據，輸出完全癱瘓的服務的數量。

---

本題實際上可以轉化為：給你\(n\)個集合\(p_{1 -> n}\)，你要把它們分成盡可能多的組，每個組內所有集合的并等于全集。

因為\(n\)比較小，所以我們可以把每個集合\(P\)（每個點自身\(+\)它相鄰的點）二進制狀壓。考慮選取一些集合時，把選取的集合也二進制狀壓（表示為\(S\)），存一下該選取狀態下可以覆蓋的狀況即可（\(cover_s\)）。

這樣我們可以得到方程：

\[f(S) = max (f(S - S_0)|S_0∈S, cover_{S_0} = S_{All})\]

技巧：二進制下的子集枚舉：

for (int S0 = S; S0 != 0; S0 = (S0 - 1) & S)

這樣為什么能實現子集枚舉呢？請讀者自行思考（笑

復雜度：\(O(\sum_{k=1->N}C(n, k) * 2 ^ n) = O(3 ^ n)\)。為什么等于后面我不會二項式定理所以不大會。

關注點：本題中的子集枚舉思想。

#include <bits/stdc++.h> using namespace std;const int N = 20;int Case, n, m, to, s[N], f[N], cho[1 << N];int main () { // freopen ("data.in", "r", stdin);while (cin >> n && n) {for (int i = 0; i < n; ++i) {cin >> m; s[i] = 1 << i;for (int j = 0; j < m; ++j) {cin >> to; s[i] |= 1 << to;} // cout << "s[" << i << "] = " << s[i] << endl;} const int All = (1 << n) - 1;for (int i = 0; i < 1 << n; ++i) {cho[i] = 0;for (int k = 0; k < n; ++k) {if ((i >> k) & 1) {cho[i] |= s[k];}}}f[0] = 0;for (int S = 1; S < (1 << n); ++S) {f[S] = 0;for (int S0 = S; S0; S0 = (S0 - 1) & S) { //枚舉S的子集 if (cho[S0] == All) {f[S] = max (f[S], f[S ^ S0] + 1);}}}cout << "Case " << ++Case << ": " << f[All] << endl;} }

轉載于:https://www.cnblogs.com/maomao9173/p/10688004.html

總結

以上是生活随笔為你收集整理的UVA11825 黑客的攻击 Hackers' Crackdown 状压DP，二进制，子集枚举的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。