题目链接：https://vjudge.net/problem/ZOJ-3471#author=yupengju
题意：不超过10种气体，两两之间相互碰撞可以产生一定的能量，如a碰b，那么b气体就消失，自身不能碰自身，问最后所能得到的最大能量
设f[s]表示最后状态为s时能得到的最大能量（最后的状态一定是某一个位为1，其他都被碰撞过为0）
则有f[s]=max(f[s],f[s‘]+a[i][j]）,这儿s的第i位为1，第j位为0；s‘的第j位为1
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[15][15],f[(1<<15)],n,i,j,s;
int main(){
while (cin>>n){
if (n==0) break;
for (i=0;i<n;i++)
for (j=0;j<n;j++) cin>>a[i][j];
memset(f,0,sizeof(f));
for (s=(1<<n)-1;s>=0;s--) //*
for (i=0;i<n;i++)
if ((s&(1<<i)))
for (j=0;j<n;j++)
if (!(s&(1<<j))) f[s]=max(f[s],f[s^(1<<j)]+a[i][j]);
int ans=0;
for (i=0;i<n;i++) ans=max(ans,f[1<<i]);
cout<<ans<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/13657906.html