zoj 3471 - Most Powerful

题目：在火星上有一些原子，他们相互碰撞会释放能量（例如a、b），并且后面的原子会消失（b消失）；

            现在给你每个原子各一个，问能产生的最大能量值。

分析：状态压缩 DP。按取数的个数为阶段进行 DP，因为与顺序无关，找到下一状态更新即可。

            如果只找一条路径，就是 TSP 问题，可将数组变为二维求解。 

说明：要不是多组数据，直接位运算+搜索就可以的。。。 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int F[ 1<<10 ];
int D[ 11 ][ 11 ];

int main()
{
    for ( int n ; scanf("%d",&n) && n ; ) {
        for ( int i = 1 ; i <= n ; ++ i )
        for ( int j = 1 ; j <= n ; ++ j )    
            scanf("%d",&D[ i ][ j ]);
        
        int S = (1<<n)-1;
        memset( F, 0, sizeof( F ) );
        for ( int b = 0 ; b <= S ; ++ b ) 
        for ( int i = 1 ; i <= n ; ++ i ) {
            if ( !(b&(1<<i-1)) ) continue;
            for ( int j = 1 ; j <= n ; ++ j ) {
                if ( !(b&(1<<j-1)) && F[ b|(1<<j-1) ] < F[ b ]+D[ i ][ j ] )
                    F[ b|(1<<j-1) ] = F[ b ]+D[ i ][ j ];
            }
        }
        
        printf("%d\n",F[ S ]);
    }
    return 0;
}

zoj 3471 - Most Powerful

原文：http://blog.csdn.net/mobius_strip/article/details/42079879