Most Powerful 题解

这题比较简单，不过有需要注意的点：
1.选取的被碰气体得是对应二进制表示为0的
2.选取的一个碰他的气体也得是对应二进制为0的（还没消失的气体）
具体看代码，有详细注释：

//1表示哪个气体被碰掉消失了 0表示气体还没被碰掉
#include <bits/stdc++.h>
using namespace std;
const int N=12;
int mp[N][N];
int dp[1<<N];//表示某个状态
//dp[i|jj]=max(dp[i]+mp[j][i])
int main()
{
    int n;
    while(~scanf("%d",&n)){
        if(n==0) break;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]);
        int len=(1<<n)-1;
        for(int i=0;i<=len;i++)
        {
            for(int j=1;j<=n;j++)//枚举将要被碰掉的气体
            {
                int jj=1<<(j-1);
                if(i&jj) continue;
                for(int k=1;k<=n;k++)//枚举用来消灭另一个气体的气体
                {
                    int kk=1<<(k-1);
                    if(kk&i) continue;
                    if(kk==jj) continue;
                    dp[i|jj]=max(dp[i|jj],dp[i]+mp[k][j]);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int ii=1<<(i-1);
            ans=max(ans,dp[len^ii]);
        }
        printf("%d\n",ans);
    }
}