题目大意是，火星上的科学家发现了N (2 <= N <= 10)个具有高能量的原子。这些原子如果两两碰撞，则会释放出大量能量，并且其中的一个会消失。科学家们已经掌握了原子碰撞的规律。现在给定这种规律，求能释放出的最大的能量。
最多不超过500组数据。最多不会超过50个大数据(N=10)。
输入：
第一行：N，表示有N个原子
然后是一个N*N的矩阵，第i行的第j个数字表示原子i与原子j碰撞，并且原子j消失的情况下，所产生的能量。
输出：
能产生的最大能量。
显然是用DP来做。
以N=3为例，p[111b]表示三个原子都存在时的能量，即0。
所求为p[100b]，p[010b]，p[001b]中的最大值。
例：p[100b]=max(p[110b]+m[1][2],p[101b]+m[1][3])。
类似于这样的做法～
#include <stdio.h>
int map[10][10];
int power[1024];
int pw[11]={1,2,4,8,16,32,64,128,256,512,1024};
int n;
int value(int status)
{
if(power[status]!=-1)
return(power[status]);
int i,j;
int ans=0,tmp;
for(i=0;i<n;i++)
{
if((status|pw[i])!=status)
{
/*第i号原子消失*/
for(j=0;j<n;j++)
{
if(i!=j && ( (status & pw[j]) != 0 ) )
{
/*第i号原子消失是因为i与j碰撞*/
tmp=value(status|pw[i])+map[j][i];
if(tmp>ans)
ans=tmp;
}
}
}
}
power[status]=ans;
return(ans);
}
main()
{
int i,j,k,t;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&map[i][j]);
for(i=0;i<pw[n];i++)
power[i]=-1;
power[pw[n]-1]=0;
/*
1表示该原子还存在
0表示该原子已不存在
*/
int ans=0;
for(i=1;i<pw[n];i*=2)
{
if(value(i)>ans)
ans=value(i);
}
printf("%d\n",ans);
}
return(0);
}
