很明顯的狀態壓縮思想了。把全集分組，枚舉每個集合的子集，看一個子集是否能覆蓋所有的點，若能，則f[s]=max(f[s],f[s^s0]+1)。即與差集+1比較。

這種枚舉集合的思想還是第一次遇到，果然太弱了。。。。~~~~

?

其中枚舉集合

for(s0=s;s0;s0=(s0-1)&s)

?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm>using namespace std;const int N=16; int pt[1<<N]; int cover[1<<N]; int f[1<<N];int main(){int n,x,icase=0;while(scanf("%d",&n),n){int c,s;for(int i=0;i<n;i++){scanf("%d",&c);s=(1<<i);for(int k=0;k<c;k++){scanf("%d",&x);s|=(1<<x);}pt[i]=s;}memset(cover,0,sizeof(cover));for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++){if((1<<j)&i){cover[i]|=pt[j];}}}memset(f,0,sizeof(f));for(int s=0;s<(1<<n);s++){f[s]=0;for(int s0=s;s0;s0=(s0-1)&s){if(cover[s0]==(1<<n)-1) f[s]=max(f[s],f[s0^s]+1);}}printf("Case %d: %d\n",++icase,f[(1<<n)-1]);}return 0; }

　　

轉載于:https://www.cnblogs.com/jie-dcai/p/4543602.html

總結

以上是生活随笔為你收集整理的UVA 11825 状态压缩DP+子集思想的全部內容，希望文章能夠幫你解決所遇到的問題。

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