合并游戏

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

4

 

描述

    大家都知道Yougth除了热爱编程之外，他还有一个爱好就是喜欢玩。

    某天在河边玩耍的时候，他发现了一种神奇的石子，当把两个石子放在一起的时候，后一个石子会消失，而且会蹦出一定数量的金币，这可乐坏了Yougth，但是他想得到最多的金币，他该怎么做?

 

输入

首先一行，一个n（1<=n<=10），表示有n个石子。

接下来n*n的一个矩阵，Aij表示第i个和第j个合并蹦出的金币值(小于10000，注意合并后j会消失)。

输出

输出最多能得到的金币值。

样例输入

20 41 030 20 112 0 11 10 0

样例输出

422

来源

上传者

代码：

//只有10个数，状态压缩一下，先枚举状态然后枚举哪两个数合并，最后找到一个状态中//只有一个数的最大的状态。#include
       
        #include
        
         #include
         
          using namespace std;int n,mp[12][12],f[1<<10];int main(){    while(scanf("%d",&n)==1){        int N=1<