题目描述

一个 $N×M$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 $8$ 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入格式

第一行有两个正整数 $N$ 和 $M$ ，表示了数字矩阵为 $N$ 行 $M$ 列。

数据范围

$1 \le N \le 10$

$1 \le M \le 100$

输出格式

输出一个整数，代表符合题目要求的最大的数字和。（样例确保数字和在 int 范围内）

样例

3 3
2 8 9
4 6 4
9 10 7

27

完成程序

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt;

// solutions 数组用于存放压缩的列选择方案
int solutions[145]; // 一定要知道这个 145 是怎么来的

// 检查状态 status 是不是一个有效的列方案
bool check(int status){
	while(status){
		if((status & __填空(1)__) ==  __填空(1)__) return false;
		status = __填空(2)__;
	}
	return true;
}

long long dp[101][145]; // 一定要知道这个 145 是怎么来的
int num[11][101];

// 按照压缩状态 status 去第 column 行选择数字，看选出来的和是多少
long long cal(int status, int column){
	long long ret = 0;
	for(int j=0;j<n;j++){
		if(status & (1<<j))
			ret += __填空(3)__;
	}
	return ret;
}

int main(){
	scanf("%d%d", &n, &m);

	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++)
			scanf("%d", &num[i][j]);
	}

	for(int i=0;i<(1<<n);i++){
		if(check(i)) solutions[++cnt] = i;
	}

	for(int i=1;i<=cnt;i++)
		dp[1][i] = __填空(4)__;

	for(int i=2;i<=m;i++){ // 递推每一列
		for(int u=1;u<=cnt;u++){ // 枚举上一列的每一种状态
			for(int v=1;v<=cnt;v++){ // 枚举当前列的每一种状态
				if(solutions[u] & solutions[v]) continue;
				if(solutions[u] & solutions[v]/2) continue;
				if(__填空(5)__) continue;
				dp[i][v] = max(dp[i][v], __填空(6)__);
			}
		}
	}

	long long ans = 0;
	for(int u=1;u<=__填空(7)__;u++){
		ans = max(ans, __填空(8)__);
	}

	cout<<ans;

	return 0;
}

填空(1)： {{ input(1) }}

填空(2)： {{ input(2) }}

填空(3)： {{ input(3) }}

填空(4)： {{ input(4) }}

填空(5)： {{ input(5) }}

填空(6)： {{ input(6) }}

填空(7)： {{ input(7) }}

填空(8)： {{ input(8) }}