[数据结构与算法]Educational DP Contest U - Grouping 状压dp

传送门

题意：

给你$n$个物品，让你将其分成任意组，在同一个组内的$i,j$会获得$a_{i,j}$的收益，让你选择一种分组方案使得收益最大。

$1\le n\le 16,|a_{i,j}|\le 1e9$

思路：

考虑到$n$很小，所以考虑状压$dp$，设$dp[i]$代表选的数状态为$i$的时候的最大收益，那么下面的问题就是如何合并转移了。。

我们利用像区间$dp$一样的思路枚举断点，这里是枚举当前状态$state$的子集，设枚举的子集是$i$，那么$state?i$就是另一个子集，我们只要保证算$state$的时候其子集的最优解已经被求出来即可，转移就是$f[state]=max(f[state],f[i]+f[state?i])$。

复杂度$O(n^2{2}^n+3^n)$，因为枚举子集的总复杂度是$3^n$。

#include<bits/stdc++.h>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define Mid (tr[u].l+tr[u].r>>1)
#define pb push_back
using namespace std;

const int N=20,INF=0x3f3f3f3f,mod=1e9+7;
typedef long long LL;

int n;
int a[N][N];
LL dp[1<<N],val[1<<N];

void solve() {
    cin>>n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            cin>>a[i][j];
        }
    }
    for(int state=1;state<1<<n;state++) {
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) if((state>>i&1)&&(state>>j&1)) {
                val[state]+=a[i][j];
            }
        }
    }
    for(int state=1;state<1<<n;state++) {
        dp[state]=val[state];
        for(int j=state&(state-1);j;j=(j-1)&state) {
            dp[state]=max(dp[state],dp[state^j]+dp[j]);
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
}

int main() {
	int _=1;
	while(_--) {
		solve();
	}

}