题意 ：
n个石子， 给你一个n*n矩阵， A[i][j]表示第i个和第j个合并蹦出的金币值， 合并完石子 j 消失。求合并所有石子后，所得的最大金币数。
分析 ：
1、 题中给的数据范围 n（1<=n<=10） 也就是说最多10个石子， 那么我们不妨用一个二进制串来表示合并的状态，1表示没被合并，0表示合并后消失了，例如 （1001）四个石子第2、3个被合并了。
2、 用d[x]来存储合并到x状态时，所得的最大金币数，例如 d[1001] 表示合并2 , 3 后所得的最大金币数。
3、 我们从开始状态开始搜索（例如4个石子：1111）， 枚举合并1个石子后的所以状态 （1110， 1101， 1011， 0111）， 再继续往下一状态求， 1110下一状 态：（0110， 1010， 1100 ）， 1101 —>（1100， 1001， 0101） ， 1011 —> （1010， 1001， 0011） ， 0111 —> （0110， 0101， 0011）, 继续往下一状态求 ……….. 用递归不断求下一状态。
1110有3种合并方法， 可以由1111中的最后一石子与前三个石子任何一个合并而来。
注意：细心会发现 1110， 1101， 1011， 0111 他们的下一状态有重复的， 所以边搜边标记， 才不会做多余的工作。
#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std; int n, a[][], d[];
int dp(int x)
{
if(d[x] != -) return d[x];//搜过的状态要标记， 这要注意！！ 不写的话会超时
int Mx = ;
if(x == ) return ;
for(int i = ; i < n; i++)
{
int mx = ;
if(x & ( << i))//枚举所有可以合并的石子， 第i+1个
{
int tem = x - ( << i);//合并完的状态，
for(int j = ; j < n; j++)
{
if(tem & ( << j))//枚举所有可以与第i+1个石子合并的石子， 求出最大的
mx = max(a[+j][i+], mx);
}
Mx = max(Mx, dp(tem) + mx);
}
}
d[x] = Mx;
return d[x];
}
int main()
{
while(scanf("%d", &n) != EOF)
{
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
scanf("%d", &a[i][j]);
memset(d, -, sizeof(d));
int ans = dp(( << n) - );
printf("%d\n", ans);
}
return ;
}