hdu-1565（方格取数（1））---状态压缩

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1565

第一次写状态压缩，感觉好强大，巧妙的运用二进制，不过不太熟练，参考了大牛的博客，想了想，恨牛叉的样子

题解：http://blog.csdn.net/jzmzy/article/details/20367939

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int s[20000]; int dp[30][20000]; int map[30][30]; int num; int n; bool ok(int x)//判断不相邻的情况 {if(x&(x>>1)) return false;//同一行存在相邻的情况return true; } void init(int m) {num = 0;for(int i = 0;i < m;i++)if(ok(i)) s[num++] = i; } int cal(int x,int t)//计算该状态下的和 {int sum = 0, j = n - 1;while(t){if(t&1) sum += map[x][j];j--;t >>= 1;}return sum; } int main() {while(~scanf("%d",&n)){if(n == 0) {puts("0");continue;}init(1<<n);for(int i = 0;i < n;i++)for(int j = 0;j < n;j++)scanf("%d",&map[i][j]);memset(dp,0,sizeof(dp));for(int i = 0;i < num;i++)dp[0][i] = cal(0,s[i]);for(int i = 1;i < n;i++){for(int j = 0;j < num;j++){int tmp = cal(i,s[j]);for(int k = 0;k < num;k++){if(s[j]&s[k]) continue;dp[i][j] = max(dp[i-1][k] + tmp,dp[i][j]);}}}int ans = 0;for(int i = 0;i < num;i++)ans = max(dp[n-1][i],ans);printf("%d\n",ans);} }

总结

以上是生活随笔为你收集整理的hdu-1565（方格取数（1））---状态压缩的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。