NYOJ 832 DP

合并游戏

时间限制：1000 ms  |  内存限制：65535 KB

难度：4

 

描述

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

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

 

输入

首先一行，一个n（1<=n<=10），表示有n个石子。
接下来n*n的一个矩阵，Aij表示第i个和第j个合并蹦出的金币值(小于10000，注意合并后j会消失)。

输出

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

样例输入

2

0 4

1 0

3

0 20 1

12 0 1

1 10 0

样例输出

4

22

来源

Yougth原创

上传者

TC_杨闯亮

代码：

//只有10个数，状态压缩一下，先枚举状态然后枚举哪两个数合并，最后找到一个状态中

//只有一个数的最大的状态。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,mp[][],f[<<];

int main()

{

    while(scanf("%d",&n)==){

        int N=<<n;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                scanf("%d",&mp[i][j]);

        memset(f,,sizeof(f));

        for(int i=;i<N;i++){

            for(int j=;j<=n;j++){

                if(i&(<<(n-j))) continue;

                for(int k=;k<=n;k++){

                    if(k==j) continue;

                    if(!(i&(<<(n-k)))) continue;

                    int sta=i^(<<(n-k));

                    f[i]=max(f[i],f[sta]+mp[j][k]);

                }

            }

        }

        int ans=;

        for(int i=;i<=n;i++){

            int sta=(N-)^(<<(n-i));

            ans=max(ans,f[sta]);

        }

        printf("%d\n",ans);

    }

    return ;

}