題意：有n臺計算機，每臺有n種服務(wù)。每臺計算機有m個鄰居，停止某臺計算某個服務(wù)時，它鄰居的相應(yīng)服務(wù)也會停止，現(xiàn)在每臺計算機可以選擇停止其中一項服務(wù)，目標(biāo)是讓盡量多的服務(wù)停止（所有計算機都停止該服務(wù)）。

·劉汝佳大白書

# include <stdio.h> # include <algorithm> using namespace std; int p[17], cover[1<<16], dp[1<<16]; int main() {int n, m, x, cas=1;while(~scanf("%d",&n),n){for(int i=0; i<n; ++i){p[i] = 1<<i;//p[i]表示停止第i部計算機時，它及它的鄰居有哪些。scanf("%d",&m);while(m--){scanf("%d",&x);p[i] |= (1<<x);}}int up = 1<<n;for(int i=1; i<up; ++i)//cover[i]表示i狀態(tài)能摧毀的計算機有哪些。{cover[i] = 0;for(int j=0; j<n; ++j)if(i&(1<<j))cover[i] |= p[j];}int all = up-1;dp[0] = 0;for(int i=1; i<up; ++i){dp[i] = 0;for(int s=i; s; s=(s-1)&i)//枚舉i的子集if(cover[s] == all)dp[i] = max(dp[i], dp[i^s]+1);//dp[i]表示i狀態(tài)時，劃分好子集的情況下，能摧毀所有計算機的最多子集。}printf("Case %d: %d\n",cas++, dp[all]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/junior19/p/6730027.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的UVA11825： Hackers' Crackdown （状压dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。