枚舉子集

二進(jìn)制枚舉子集下面代碼就是枚舉的s的子集（二進(jìn)制狀態(tài)壓縮）

for(int i=s;i;i=(i-1)&s){//i表示的就是s的子集}

枚舉所有子集的子集的時(shí)間復(fù)雜度
比如一個(gè)有n個(gè)元素構(gòu)成的集合，子集的數(shù)量是$2^n$，現(xiàn)要求枚舉所有子集的子集。
一個(gè)有k個(gè)元素構(gòu)成的集合，子集的數(shù)量是$2^k$

考慮$n$個(gè)元素構(gòu)成的集合子集：
元素個(gè)數(shù)是$0$的集合個(gè)數(shù)是$C_n^0$
元素個(gè)數(shù)是$1$的集合個(gè)數(shù)是$C_n^1$
$\dots$
于是有以下等式
$$C_n^0\times 2^0+C_n^1\times 2^n+?+C_n^n\times 2^n=(1+2{)}^n=3^n$$

由此最終需要枚舉$3^n$個(gè)狀態(tài)，時(shí)間復(fù)雜度為$\Theta (3^n)$

Close Group

首先暴力預(yù)處理出所有滿足題意的連通塊，連通塊中的點(diǎn)兩兩之間有直接邊。$\Theta (n^2+2^n)$

狀態(tài)壓縮dp
狀態(tài)表式：$f_i$表示選擇$i$這些點(diǎn)構(gòu)成的最少數(shù)量的團(tuán)
狀態(tài)計(jì)算：枚舉$i$狀態(tài)的子集$j$，于是有$f_i=min(f_i,f_j+f_{i\oplus j})$
時(shí)間復(fù)雜度：枚舉所有狀態(tài)的子集即上述證明$\Theta (3^n)$

時(shí)間復(fù)雜度$\Theta (n^2+2^n+3^n)$

$3^{18}=387420489$差不多能過(guò)，誰(shuí)讓狀態(tài)壓縮就是那么玄學(xué)呢

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=20; bool ok[1<<N]; int g[N][N]; int dp[1<<N]; int main() {IO;int T=1;//cin>>T;while(T--){int n,m;cin>>n>>m;while(m--){int a,b;cin>>a>>b;--a,--b;g[a][b]=g[b][a]=1;}for(int i=0;i<1<<n;i++){vector<int> t;for(int j=0;j<n;j++)if(i>>j&1) t.push_back(j);ok[i]=1;for(int j=0;j<t.size();j++)for(int k=j+1;k<t.size();k++)if(!g[t[j]][t[k]]) ok[i]=0;}for(int i=0;i<1<<n;i++) dp[i]=n+1;dp[0]=0;for(int i=1;i<1<<n;i++){if(ok[i]) dp[i]=1;for(int j=i;j;j=(j-1)&i)dp[i]=min(dp[i],dp[j]+dp[j^i]);}cout<<dp[(1<<n)-1]<<'\n';}return 0; }

E - Or Plus Max

對(duì)于K的子集一定滿足$iorj\le K$
枚舉子集，記錄子集的最大值和次大值，相加即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=500010; int a[N]; int mx[N],f[N]; int main() {IO;int T=1;//cin>>T;for(int ca=1;ca<=T;ca++){int n;cin>>n;for(int i=0;i<1<<n;i++){cin>>a[i];mx[i]=a[0];}for(int i=0;i<1<<n;i++)for(int j=i;j;j=(j-1)&i){f[i]=max(f[i],a[j]+mx[i]);mx[i]=max(mx[i],a[j]);}for(int i=1;i<1<<n;i++) {f[i]=max(f[i-1],f[i]);cout<<f[i]<<'\n';}}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的枚举子集dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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