HDU 1565 方格取数(1) (状压dp)

Problem Description 给你一个n*n的格子的棋盘，每个格子里面有一个非负数。 从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。 Input 包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20) Output 对于每个测试实例，输出可能取得的最大的和 Sample Input 3 75 15 21 75 15 28 34 70 5 Sample Output 188 思路：dp[i][j]表示第i行为第j种状态时的最大和，枚举第i-1行的状态dp[i-1][k]，如果满足两状态相与为0就可以转移。

剪枝：把一行中满足条件的状态储存下来，只要枚举这些状态即可。题目中所说n<=20实际上n<=16。

#include <iostream> #include <stdio.h> #include <cmath> #include <algorithm> #include <iomanip> #include <cstdlib> #include <string.h> #include <vector> #include <queue> #include <stack> #include <ctype.h> using namespace std; int n; int a[25][25]; int temp[70000][25]; int cnt[25][70000]; //第i行第j种状态时的和 int dp[25][70000]; int ans[25]; //ans[i]=max(dp[i][j]) int can[70000]; //表示可行的状态 int sum=0; void init() { memset(temp,0,sizeof(temp)); for(int i=0;i<1<<16;i++) { int x=i; int cnt=0; while(x>0) { temp[i][cnt++]=x%2; x/=2; } int flag=0; for(int j=0;j<=20;j++) { if(temp[i][j]==1&&temp[i][j+1]==1) { flag=1; break; } } if(flag==0) { can[sum++]=i; } } } int main() { init(); while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { for(int j=0;j<n;j++) { scanf("%d",&a[i][j]); } } memset(dp,0,sizeof(dp)); memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { for(int j=0;j<sum;j++) { int val=0; for(int k=0;k<n;k++) { if(temp[can[j]][k]==1) val+=a[i][k]; } cnt[i][j]=val; } } for(int i=1;i<=n;i++) { for(int j=0;j<sum;j++) { for(int k=0;k<sum;k++) { if((can[j]&can[k])==0) { dp[i][j]=max(dp[i][j],dp[i-1][k]+cnt[i][j]); ans[i]=max(ans[i],dp[i][j]); } } } } cout<<ans[n]<<endl; } return 0; }