#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=16;
int a[N][N];
LL dp[1<<N],va[1<<N];

int main()
{
	int n;scanf("%d",&n);
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]);

	memset(va,0,sizeof(va));
	//预处理状态S分成1个组的收益 
	for(int S=1;S<(1<<n);S++)
		for(int i=0;i<n;i++) if((1<<i)&S)
			for(int j=i+1;j<n;j++) if((1<<j)&S)
				va[S] += a[i][j];

	memset(dp,0,sizeof(dp));

	for(int S=0;S<(1<<n);S++)//枚举状态 S
	{
		
		for(int s=S;s;s=S&(s-1))//这一步枚举S的所有非空子集: 假设S=01100111，那么S的所有非空子集为：
			dp[S] = max(dp[S],dp[S-s]+va[s]);
	}
	printf("%lld\n",dp[(1<<n)-1]);
	return 0;
}

为什么for(int s=S;s;s=S&(s-1)) 能枚举S的所有非空子集 假设S=01100111，那么S的所有非空子集为：

• 01100111
• 01100110
• 01100101
• 01100100
• 01100011
• 01100010
• 01100001
• 01100000
• 01000111
• 01000110
• 01000101
• 01000100
• 01000011
• 01000010
• 01000001
• 01000000
• 00100111
• 00100110
• 00100101
• 00100100
• 00100011
• 00100010
• 00100001
• 00100000
• 00000111
• 00000110
• 00000101
• 00000100
• 00000011
• 00000010
• 00000001
• 00000000（结束） 这段代码的核心是利用位运算来枚举状态S的所有非空子集。具体来说，s=S&(s-1)的操作会将s的最低位1变为0，从而在下一次循环中得到下一个子集。 这样可以确保每次循环都能得到S的一个非空子集，直到s变为0为止。