AT_dp_uGrouping题解

写这个只是为了回忆状压dp（子集dp）一年前学的现在才顿悟。

题意

有 n n n只兔子，编号 1 1 1至 n n n。

给出二维数组 a 1... n , 1... n a_{1...n,1...n} a1...n,1...n​其中 a i , j a_{i,j} ai,j​表示第 i i i只兔子和第 j j j只兔子的兼容度，

数据保证 a i , j = 0 , a i , j = a j , i a_{i,j}=0, a_{i,j}=a_{j,i} ai,j​=0,ai,j​=aj,i​。

现在你需要把这 n n n只兔子分成若干组，使得每只兔子仅属于一个组。

当分组结束后，对于 1 ≤ i < j ≤ n 1\le i<j\le n 1≤i<j≤n，你将会获得 a i , j a_{i,j} ai,j​元钱，前提是第 i i i只兔子和第 j j j只兔子分在了同一组。应该如何分组，才能使得最终赚的钱最多。

输出赚得最多的钱数。

n ≤ 18 n\le 18 n≤18

思路

看见给出的 n n n异常的小，考虑使用状压dp来做。

把最终所有兔子分好组的状态记作 t o t = ( 1111. . n 个 1 . . 1111 ) 2 tot=(1111.._{n个1}..1111)_2 tot=(1111..n个1​..1111)2​，那么每一个组看作严格 t o t tot tot的子集，全部与起来就是 t o t tot tot了。

这不就是背包问题么？只不过要装的是每个状态 s s s的严格子集 s u b sub sub而已， s u b sub sub的贡献（即兼容度）可以预处理出来。

设 f s f_s fs​表示当所有组的状态与起来为 s s s时，最大兼容度。 s u m s sum_s sums​表示组的集合恰为 s s s时的实际兼容度大小。

考虑 Θ ( 2 n ⋅ n 2 ) \Theta (2^n\cdot n^2) Θ(2n⋅n2)预处理 s u m sum sum数组。典型地， f f f的dp公式可以很好地写出来，只是下标换成集合与其子集了： f s = max ⁡ s u b ⊆ s f s − s u b + s u m s u b f_s=\max_{sub\subseteq s}f_{s-sub}+sum_{sub} fs​=sub⊆smax​fs−sub​+sumsub​

诶，怎么快速枚举 s s s的严格子集 s u b sub sub呢？

初始时 s u b = s sub=s sub=s，那么可以强制地把 s u b − 1 sub-1 sub−1，把最靠后的位置是 1 1 1的地方强变成 0 0 0，再与上 s s s，枚举前面的 1 1 1

是不是讲得很迷糊？还是硬枚举 1 1 1个例子吧。（其实就是模拟人最本能的多项枚举策略）

1111 1111 1111 1110 1110 1110 1101 1101 1101 1100 1100 1100 1011 1011 1011 1010 1010 1010 1001 1001 1001 1000 1000 1000 0111 0111 0111 0110 0110 0110 0101 0101 0101 0100 0100 0100 0011 0011 0011 0010 0010 0010 0001 0001 0001

我们可以将不属于 s s s的元素看作 0 0 0，属于 s s s但不属于 s u b sub sub的元素看作 1 1 1，属于 s u b sub sub的元素看作 2 2 2。对于每个兔子，都有 3 3 3种可能的状态，所以总时间复杂度是 Θ ( 3 n ) \Theta (3^n) Θ(3n)

总的时间复杂度 Θ ( 2 n ⋅ n 2 + 3 n ) \Theta(2^n\cdot n^2+3^n) Θ(2n⋅n2+3n)

代码 #include<bits/stdc++.h> using namespace std; #define ll long long const ll N=18,inf=0x7f7f7f7f; ll n,a[N][N]; ll f[1<<N],sum[1<<N]; //f(s):并集为s，最大得分 //sum(s):集合恰为s，实际得分 int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]); for(int s=0;s<(1<<n);s++) { for(int i=1;i<=n;i++) { if(s&(1<<(i-1)))//选了i { for(int j=i+1;j<=n;j++) if(s&(1<<(j-1)))sum[s]+=a[i][j];//选了j } } } for(int s=0;s<(1<<n);s++) for(int sub=s;sub;sub=((sub-1)&s))//枚举s的子集sub f[s]=max(f[s],f[s^sub]+sum[sub]); printf("%lld",f[(1<<n)-1]); return 0; }