ZOJ 3471 Most Powerful

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3471

题目：有N个原子，两两相撞会释放出能量，并且第 i 个原子跟第 j 个原子相撞后原子j会消失，给出一个矩阵，P[i][j]代表第 i 个原子跟第 j 个原子相撞释放的能量值，求这些原子相撞所能释放的最大能量值。

分析：状态压缩，最多2^10种状态。

集合S表示所有原子集合， i 与 j 相撞， 状态转移方程为：

dp[ S ^ (1 << j) ] = max( dp[ S ^ (1 << j) ], dp[S]+ map[i][j]);

撞击后j不在集合S中                                        i, j都在集合S中，未撞击前

#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAXN = 1 << 11;

int map[11][11];
int dp[MAXN];
int n;

int max( int a, int b )
{
    return a > b ? a : b;
}

int DP()
{
    for ( int S = (1 << n) - 1; S >= 0; S-- )
    {
        for ( int i = 0; i < n; i++ )
            if ( S & ( 1 << i ) )
            {
                for ( int j = 0; j < n; j++ )
                    if ( i != j && S & ( 1 << j ) )
                    {
                        dp[ S ^ (1 << j) ] = max( dp[ S ^ (1 << j) ], dp[S]+ map[i][j]);
                    }
            }
    }

    int MAX = -1;
    for ( int i = 0; i < (1 << n); i++ )
        MAX = max( MAX, dp[i] );
    return MAX;
}

int main()
{
    while ( scanf( "%d", &n ), n )
    {
        memset(dp, 0, sizeof(dp) );
        for ( int i = 0; i < n; i++ )
            for ( int j = 0; j < n; j++ )
                scanf( "%d", &map[i][j] );

        printf( "%d\n", DP() );
    }
    return 0;
}