本文主要是介绍NYOJ 832合并游戏(状态压缩dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
大家都知道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
这一题典型的状态压缩dp, 直接解释状态压缩方程。这题状态压缩方程不好用式子表示，我大概举个例子讲一下怎么转移的。首先要来一个数来表示目前的一个状态，比如n==8,就是有8个石子，然后接着就是假设有一个状态10101101(十进制173)，0表示石子已经没掉了，1表示这个石子还在，那么这个状态其实可以由11101101或者10111101或者10101111这三个状态转化而来，而且就这三个， 而这三个状态相比于10101101这个数多出来的1就是相当于与10101101中的1表示的石子合并时没掉的。这个1应该是变成10101101中的0，所以每找到一个0，就枚举这个状态中所有1，因为与可能是这个1让原来的1没掉了，变成了零。以上举了个例子应该就清楚大概思路了清楚了。
AC代码：
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <vector>
using namespace std;
vector<int> v[20];
int bit[20], a[20][20], dp[15000];
int n;
int cal(int temp){int cnt=0;for(int i=1; i<=n; i++){if(!(temp&1)){cnt++;}temp=(temp>>1);}return cnt;
}
int main(){int i, j, k, temp1, l, ans;bit[1]=1;for(i=2; i<=10; i++){bit[i]=(bit[i-1]<<1);}while(scanf("%d", &n)!=EOF){if(n==1){scanf("%d", &temp1);printf("0\n");continue;}memset(dp, 0, sizeof(dp));dp[(1<<n)-1]=0;for(i=0; i<=10; i++){v[i].clear();}for(i=1; i<=n; i++){for(j=1; j<=n; j++){scanf("%d", &a[i][j]);}}for(i=1; i<=(1<<n)-1; i++){v[cal(i)].push_back(i);}for(i=1; i<=n-1; i++){for(j=0; j<=v[i].size()-1; j++){temp1=v[i][j];for(k=1; k<=n; k++){if(!(temp1&1)){for(l=1; l<=n; l++){if(v[i][j]&bit[l]){dp[v[i][j]]=max(dp[v[i][j]], dp[(v[i][j]|bit[k])]+a[l][k]);}}}temp1=(temp1>>1);}}}ans=0;for(i=0; i<=v[n-1].size()-1; i++){ans=max(ans, dp[v[n-1][i]]);}printf("%d\n", ans);}return 0;
}
这篇关于NYOJ 832合并游戏(状态压缩dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
