转载

nyoj832 合并游戏（状态压缩DP）

题意：

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[15][15], d[10000]; int dp(int x) {  if(d[x] != -1) return d[x];//搜过的状态要标记， 这要注意！！ 不写的话会超时  int Mx = 0;  if(x == 0) return 0;  for(int i = 0; i < n; i++)  {   int mx = 0;   if(x & (1 << i))//枚举所有可以合并的石子， 第i+1个   {    int tem = x - (1 << i);//合并完的状态，    for(int j = 0; j < n; j++)    {     if(tem & (1 << j))//枚举所有可以与第i+1个石子合并的石子， 求出最大的      mx = max(a[1+j][i+1], mx);    }    Mx = max(Mx, dp(tem) + mx);   }  }  d[x] = Mx;  return d[x]; } int main() {  while(scanf("%d", &n) != EOF)  {   for(int i = 1; i <= n; i++)    for(int j = 1; j <= n; j++)     scanf("%d", &a[i][j]);   memset(d, -1, sizeof(d));   int ans = dp((1 << n) - 1);   printf("%d/n", ans);  }  return 0; }