首页 > 代码库 > NYOJ 832 合并游戏

NYOJ 832 合并游戏

2024-07-18 20:32:35   221人阅读

合并游戏

时间限制：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_杨闯亮

 




解题：在wdd的指导，终于搞定了！wdd,神dp啊！状压dp。。。

二进制1111表示还剩4个没有选，二进制1101表示还剩三个没选，1101可以由1111与另外三个合并转移而来。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 int mp[12][12],n;18 vector<int>g[100];19 bool vis[20480];20 int dp[100000];21 void init() {22     int i,j,k,temp,v,u;23     memset(vis,false,sizeof(vis));24     for(i = 0; i < 100; i++) g[i].clear();25     g[0].push_back((1<<n)-1);26     g[n].push_back(0);27     vis[0] = true;28     vis[(1<<n)-1] = true;29     for(i = 1; i <= n; i++) {30         for(j = 0; j < g[i-1].size(); j++) {31             temp = g[i-1][j];32             for(k = 0; k < n; k++) {33                 u = temp&(1<<k);34                 if(u) {35                     v = temp^(1<<k);36                     if(vis[v]) continue;37                     vis[v] = true;38                     g[i].push_back(v);39                 }40             }41         }42     }43 }44 int go(int x){45     char s[20];46     int pos[120],m = 0,i,j,y,theMax = 0;47     for(i = 0; i < n; i++)48         if(x&(1<<i)) pos[m++] = i;49     for(i = 0; i < n; i++){50         if((x&(1<<i)) == 0){51             y = x^(1<<i);52             for(j = 0; j < m; j++){53                 theMax = max(theMax,dp[y]+mp[pos[j]][i]);54             }55         }56     }57     return theMax;58 }59 int main() {60     int i,j,ans;61     while(~scanf("%d",&n)) {62         init();63         for(i = 0; i < n; i++) {64             for(j = 0; j < n; j++)65                 scanf("%d",mp[i]+j);66         }67         memset(dp,0,sizeof(dp));68         for(i = 1; i <= n; i++){69             for(j = 0; j < g[i].size(); j++){70                 dp[g[i][j]] = go(g[i][j]);71             }72         }73         for(ans = i = 0; i < g[n-1].size(); i++)74             ans = max(ans,dp[g[n-1][i]]);75         printf("%d\n",ans);76     }77     return 0;78 }
View Code

 


联系
我们