牛客第五场 E independent set 1 —— 状压 dp

本文主要是介绍牛客第五场 E independent set 1 —— 状压 dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 个点，求所有能组成的集的最大独立集的和

解题思路：

    $n\le 26$，所以可以 状压 $dp$
    $a_x$ 表示 $x$ 这个点连的边的状态
    $l{b}_x$ 表示 $x$ 二进制中最低位为 $1$ 的位置
    __$builtin$_$ctz(x)$ 表示 $x$ 末尾有多少个 $0$
    $dp[x]$ 表示 $x$ 这个集的最大独立集的 $size$

    然后随便删去一个点，$x$ 的 $dp$ 值即为删去后的答案与未删的答案 $+1$ 取 $max$
    $dp[x]=max(dp[x⨁lb],char(dp[x$ & $(a[\_\_builtin\_ctz(x)])]+1))$

    $PS：$题目卡内存。。用 $4$ 字节的 $int$ 会爆
               需要用 $1$ 字节的 $char$ ，最多只能存 $255＞n$

核心：位元状压dp与独立集的应用

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
int n, m, a[26];
ll ans;
char dp[(1<<26) + 5];int lowbit(int x){return x & (-x);
}int main() {scanf("%d%d", &n, &m);while(m--){int u, v;scanf("%d%d", &u, &v);a[u] |= (1<<v); a[v] |= (1<<u); }for(int i=0; i<n; i++) a[i] |= (1<<i);for(int s=1; s<(1<<n); s++){int lb = lowbit(s);dp[s] = max(dp[s^lb], char(dp[s&(~a[__builtin_ctz(s)])] + 1));ans += int(dp[s]);}printf("%lld\n", ans);
}

这篇关于牛客第五场 E independent set 1 —— 状压 dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---