HDUOJ 1565 方格取数(1)

题目链接

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 ~ 我们对每一列的取数可以用二进制表示，有 $n$ 位显然就是 $[0,2^n)$，那么对相邻的两行 $x,y$ 只需要判断 $x\&y=0$ 即可，如果等于 $0$ 证明两行无相邻点。但此时复杂度还是太高了，我们想到一行中也不能存在相邻点，也就是说这个数的二进制里不能有相邻的 $1$，判断只需用 $x\&(x>>1)=0$ 判断即可，为什么呢？因为只要二进制中无连续的 $1$，该数与其错一位后进行与运算一定等于 $0$，可以自己列几个数字计算一下，这样筛一下数后复杂度就能大幅降低，下面考虑 DP 我们用 $dp[i][j]$ 表示第 $i$ 行以 $j$ 作为该行状态的最大值，$cal(i,j)$ 函数计算 $i$ 行以 $j$ 为状态后的取值，那么我们可以枚举 $i-1$ 行所有符合条件的最大值加上 $cal(i,j)$，即: $$dp[i][j]=max(dp[i][j],dp[i-1][k]+cal(i,j)),k\&j=0$$ AC代码如下：

#include<bits/stdc++.h> using namespace std; int n,a[20][1<<18],dp[20][1<<18]; int num[1<<18]; int cal(int x,int y){ int sum=0; for(int i=0;i<n;i++){ if((1<<i)&y) sum+=a[x][i+1]; } return sum; } int main(){ while(~scanf("%d",&n)){ int cnt=0,ans=0; for(int i=0;i<(1<<n);i++) if((i&(i>>1))==0) num[++cnt]=i; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ for(int j=1;j<=cnt;j++){ int val=cal(i,num[j]); for(int k=1;k<=cnt;k++){ if((num[j]&num[k])==0){ dp[i][j]=max(dp[i][j],dp[i-1][k]+val); } } } } for(int i=1;i<=cnt;i++) ans=max(ans,dp[n][i]); printf("%d\n",ans); } return 0; }