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的最大值，首先先预处理出一行时不冲突的状态，那么我们从第一行开始处理，到最后一行就能得到最大值了，然后再转移到与当前一行
不冲突的下一行的状态，滚动数组处理
#include
#include
#include
#include
using namespace std; const int maxn = 1<<21; int status[maxn], n, cnt; int dp[2][maxn]; int ans, g[22][22]; void init() { cnt = 0; for (int i = 0; i < (1<<20); i++) { if (i & (i << 1)) continue; else status[cnt++] = i; } } int main() { init(); while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &g[i][j]); if (n == 0) { printf("0\n"); continue; } int tot = 1 << n; ans = 0; for (int i = 0; status[i] < tot; i++) { dp[0][i] = 0; for (int j = 0; j < n; j++) if (status[i] & (1<