最近，火星研究人员发现了N个强大的原子。他们互相都不一样。

这些原子具有一些性质。当这两个原子碰撞时，其中一个原子会消失，产生大量的能量。
研究人员知道每两个原子在碰撞时的能释放的能量。
你要写一个程序，让它们碰撞之后产生最多的总能量。

【输入格式】

第一行是整数N（2 <= N <= 10），这意味着有N个原子：A1到AN。

然后下面有N行，每行有N个整数。
在第i行中的第j个整数表示当i和j碰撞之后产生的能量，并且碰撞之后j会消失。
所有整数都是正数，且不大于10000。

【分析题目】

举例分析问题 ，N=3， M数组如下

0  3  7  

2  0  6  

5  2  0 

考虑用动态规划。

用f{3,2,1}表示原问题，则状态是一个集合。

如何找子问题?

取集合里面的两个原子弹出来碰撞， 这样会有一个原子弹消失，那么原子弹的集合就会少一个元素，从而变成了子问题。

（1）那原子弹1碰撞原子弹2，得到能量3，原子弹2消失，变成子问题： f{3,1}，  记 A = 3 + f{3,1}

（2）那原子弹1碰撞原子弹3，得到能量7，原子弹3消失，变成子问题： f{2,1}，  记 B = 7 + f{2,1}

（3）那原子弹2碰撞原子弹1，得到能量2，原子弹1消失，变成子问题： f{3,2}，  记 C = 2 + f{3,2}

（4）那原子弹2碰撞原子弹3，得到能量6，原子弹3消失，变成子问题： f{2,1}，  记 D = 6 + f{2,1}

（5）那原子弹3碰撞原子弹1，得到能量5，原子弹1消失，变成子问题： f{3,2}，  记 E =  5 + f{3,2}

（6）那原子弹3碰撞原子弹2，得到能量2，原子弹2消失，变成子问题： f{3,1}，  记 F =  2 + f{3,1}

原问题f{3,2,1} = max( A, B, C, D, E, F), 所以只有能求出ABCDEF，就能求出原问题。

下面分析如何A，其他BCDEF同理求。

A = 3 + f{3,1}，只要求出子问题f{3,1}就能求出A。

如何求f{3,1}? 分两种情况：

（1）原子弹1碰撞原子弹3,得到能量7，原子弹3消失，变成子问题：f{1}，易知f{1} = 0

（2）原子弹3碰撞原子弹1,得到能量5，原子弹1消失，变成子问题：f{3}，易知f{3} = 0

所以 A = 3 + f{3,1} = max(7+0, 5+0) = 3 + 7 = 10。

同理可以求出:

B= 7 + f{2,1} = 7 + 3 = 10

C = 2 + f{3,2} = 2 + 6 = 8

D = 6 + f{2,1} = 6 + 3 = 9

E =  5 + f{3,2} = 5 + 6 = 11

F =  2 + f{3,1} = 2 + 7 = 9

所以原问题f{3,2,1} = max(A,B,C,D,E,F) = max(10,8,9,11,9) = 11

通过上面的分析可以发现， 子问题集合的元素个数比原问题集合的元素个数少。

所以我们计算顺序是： 先算集合元素个数少的，再算集合元素个数多的。

这种计算顺序（即动态规划的阶段）虽然正确性没问题，但是比较麻烦。

因为状态是一个集合，表示起来比较麻烦， 例如 f{3,1}，在C++如何表示？

f[{3,1}]？这样肯定不行（除非用f是map类型）， f数组的下标希望是整型。

接下来，我们换一种计算顺序，不再是从集合元素个数从少算到多。

用新的计算顺序来计算上面的样例：

可以发现，上面的计算顺序是按照十进制数1至7所对应的集合的来计算。

这样编程就容易了：

for(int i=1;  i<=7;  i++)   f[i] = max( ...... ); 

但是有一个问题，在计算f[i]时，会不会出现后效性？（动态规划要满足无后效性）

for(int i=1;  i<=7;  i++) 

{

       f[i] = ？; 

       因为i是从小到大的计算顺序，所以在计算f[i]时，必须保证f[i]的值只和f[0],f[1],f[2],...f[i-1]有关，

       f[i]的值不能和f[i+1],f[i+2],......有关。

       即f[i]无后效性。

}  

幸运的是，f[i]的计算过程确实是无后效性。

下面看看计算f[7]时，是如何计算的。

首先，十进制数7表示的二进制数是111，所以111表示的集合是{3,2,1}。

求f[7]实际就是求f{3,2,1}，根据前面的分析可以知道：

取集合里面的两个原子弹出来碰撞， 这样会有一个原子弹消失，那么原子弹的集合就会少一个元素，从而变成了子问题。

（1）那原子弹1碰撞原子弹2，得到能量3，原子弹2消失，变成子问题： f{3,1} =  f[5]，  记 A = 3 + f[5]

（2）那原子弹1碰撞原子弹3，得到能量7，原子弹3消失，变成子问题： f{2,1}  = f[3]，  记 B = 7 + f[3]

（3）那原子弹2碰撞原子弹1，得到能量2，原子弹1消失，变成子问题： f{3,2} =  f[6]，  记 C = 2 + f[6]

（4）那原子弹2碰撞原子弹3，得到能量6，原子弹3消失，变成子问题： f{2,1} =  f[3]，  记 D = 6 + f[3]

（5）那原子弹3碰撞原子弹1，得到能量5，原子弹1消失，变成子问题： f{3,2} =  f[6] ，  记 E =  5 + f[6]

（6）那原子弹3碰撞原子弹2，得到能量2，原子弹2消失，变成子问题： f{3,1}  = f[5] ，  记 F =  2 + f[5]

所以f[7]只与子问题f[3]、f[5]、f[6]有关。

因为 for(int i=1;  i<=7;  i++)   f[i] = max( ...... );  所以在计算f[7]时，f[3]、f[5]、f[6]肯定已经计算出来了。

其实很容易知道，如果f[j]是f[i]的子问题，那么j一定小于i。证明？

其实很简单，因为j是i去掉1个原子弹之后得到的集合，所以j对应的二进制数一定小于i对应的二进制数，

那么j对应的十进制数也一定小于i对应的十进制数。

所以本题的程序框架是： 

int   s = (1<<N) - 1;   //即s是一个十进制数，s代表全集，包含N个原子弹，s={N,N-1,......,2,1}， 

//    集合、 二进制数、 十进制数， 三者是一一对应的关系！

for(int i=1;   i<=s;  i++)  //按照十进制数从1至s的顺序来计算f[i]

{

        f[i] = ?  //十进制数i，展开后是二进制数， 代表一个集合。

}

cout<<f[s]<<endl;

进一步具体地：

int   s = (1<<N) - 1;   //即s是一个十进制数，s代表全集，包含N个原子弹，s={N,N-1,......,2,1}， 

//    集合、 二进制数、 十进制数， 三者是一一对应的关系！

for(int i=1;   i<=s;  i++)  //按照十进制数从1至s的顺序来计算f[i]

{

       第一步：把十进制数i对应的集合，所包含的原子弹分离出来并保存到临时数组A。

                    例如： i = 22，那么A[] = {5,3,2}，则十进制数22所代表的集合包含了第2,3,5个原子弹。

       第二步： 从A数组里面任意取出两个原子弹（不妨假设是X和Y），分别用X碰撞Y，用Y碰撞X，

                     都能变成子问题，维护好f[i]的值。

}

cout<<f[s]<<endl;

更进一步具体地：

int   s = （1<<N) - 1;   //即s是一个十进制数，s代表全集，包含N个原子弹，s={N,N-1,......,2,1}， 

//    集合、 二进制数、 十进制数， 三者是一一对应的关系！

for(int i=1;   i<=s;  i++)  //按照十进制数从1至s的顺序来计算f[i]

{

       第一步：把十进制数i对应的集合，所包含的原子弹分离出来并保存到临时数组A。

                    例如： i = 22，那么A[] = {5,3,2}，则十进制数22所代表的集合包含了第2,3,5个原子弹。

                    可以通过枚举第j个原子弹是否属于十进制数i所表示的集合，从而产生A数组。

                     int tot = 0;  //临时变量，表示十进制数i所表示的集合，总共包含tot个原子弹。

                     for(int j=N; j>=1;  j--)  //判断十进制数i所表示的集合是否包含第j个原子弹

                     {

                                    int  C = 1<<(j-1);

                                    if(  (i&C) > 0)   A[++tot] = j;  //说明十进制数i所表示的集合包含第j个原子弹

                     }

       第二步： 从A数组里面任意取出两个原子弹（不妨假设是X和Y），分别用X碰撞Y，用Y碰撞X，都能变成子问题。

                      for(int u = 1;  u < tot;  u++)

                          for(int  v = u + 1;  v <= tot;  v++)

                          {

                                    int  X = A[u];

                                    int  Y = A[v];

                                    （1）用X碰撞Y，得到能量M[X][Y], 子问题是什么？

                                             因为碰撞后第Y个原子弹消失，那么子问题就是从十进制数i代表的集合里面去掉第Y个原子弹，如何表示子问题的状态呢？

                                             第Y个原子弹对应的二进制数是:  1 << (Y-1) , 不妨记为 Z = 1<<(Y-1)；

                                             根据前面所学的集合与二进制的关系，子问题的状态为： i - Z =  i ^ Z，  即i异或Z

                                              所以  f[i] = max(f[i],  M[X][Y] + f[i^Z]);

                                     （2）用Y碰撞X，得到能量M[Y][X], 子问题是什么？

                                             因为碰撞后第X个原子弹消失，那么子问题就是从十进制数i代表的集合里面去掉第X个原子弹，如何表示子问题的状态呢？

                                             第X个原子弹对应的二进制数是:  1 << (X-1) , 不妨记为 Z = 1<<(X-1)；

                                             根据前面所学的集合与二进制的关系，子问题的状态为： i - Z =  i ^ Z，  即i异或Z

                                             所以  f[i] = max(f[i],  M[Y][X] +  f[i^Z];

                          } 

}

cout<<f[s]<<endl;

时间复杂度: O(2^n * n * n )