首页 > 代码库 > zoj 3471 - Most Powerful

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