nyoj832 合並游戲（狀態壓縮DP）

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
#include
#include
#include
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;
}