ZOJ 4257 MostPowerful（状压DP，简单）

题目大意：不超过10种气体，两两之间相互碰撞可以产生一定的能量，如a碰b，那么b气体就消失，自身不能碰自身，问最后所能得到的最大能量。

原代码链接：http://blog.csdn.net/accry/article/details/6607703

题解：感觉这个题是我做状态压缩的几个题中最简单的了，这存图用a数组就可以了，也不用处理a数组（有的求路径的题要用弗洛伊德处理原数组），因为碰撞是不可逆的。

接着就用s开始从0枚举状态到1<<N-1，还要注意去掉不可能的情况！！

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int MAXN=10;
const int MAX_S=1<<10;

int a[MAXN+1][MAXN+1];
int dp[MAX_S];
int N;

int main()
{
    while(cin>>N,N)
    {
        for (int i=0; i<N; i++)
            for (int j=0; j<N; j++)
                scanf("%d",&a[i][j]);
        memset(dp,0,sizeof(dp));
        int full=1<<N;
        for (int s=0; s<full; s++)/**< 这块是状态的枚举，必须小于1<<N，
            且从0开始,并且，一般都用S做循环变量*/
        {
            for (int i=0; i<N; i++)
            {
                if ((s&(1<<i))) continue;//去掉i自己的情况
                for (int j=0; j<N; j++)
                {
                    if (i==j) continue;//去掉相同的情况
                    if ((s&(1<<j))) continue;//去掉j自己的情况
                    int newS=s+(1<<j);
                    dp[newS]=max(dp[newS],dp[s]+a[i][j]);
                }
            }
        }
        int ans = 0;
        for(int s = 0; s < full ; ++s)
            ans = max(ans,dp[s]);
        printf("%d
",ans);
    }
}