给你一个n * n的格子的棋盘，每个格子里面有一个非负数。从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

状态压缩DP，设dp[i][j]为第 i 行状态为 j 的最大和，则dp[i][j] = \\max(dp[i – 1][k]) + sum_j，其中，sum_j表示状态为 j 时所能得到的和，j表示第i行的状态，k表示第i – 1行的状态，且要满足 k 与 j 中的数不相邻。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 30000;
int state[N], a[25][25];
int dp[25][N];
int main()
{
  int n;
  while (~scanf("%d", &n)) {
    int cnt = 0;
    for (int i = 0; i < 1 << n; i++) {
      if (i & i << 1)
        continue;
      state[cnt++] = i;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < n; j++) {
        scanf("%d", &a[i][j]);
      }
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < cnt; j++) {
        for (int k = 0; k < n; k++) {
          //把状态 j 的和求出来
          if (state[j] & 1 << k) {
            dp[i][j] += a[i][k];
          }
        }
        int tmp = 0;
        //找出第 i - 1 行中最大的和
        for (int k = 0; k < cnt; k++) {
          //如果状态 j 与状态 k 有相邻的，则跳过
          if (state[j] & state[k]) {
            continue;
          }
          tmp = max(tmp, dp[i - 1][k]);
        }
        dp[i][j] += tmp;
      }
    }
    int ans = 0;
    for (int i = 0; i < cnt; i++) {
      ans = max(ans, dp[n][i]);
    }
    printf("%d\n", ans);
  }
  return 0;
}