衡水企业网站设计报价,计科专业毕设做网站,wordpress调用文章字数,备案网站用户名是什么目录 1.题目
题目描述
输入格式
输出格式
输入输出样例
说明/提示
2.AC 1.题目
题目描述
一个N \times MNM的由非负整数构成的数字矩阵#xff0c;你需要在其中取出若干个数字#xff0c;使得取出的任意两个数字不相邻#xff08;若一个数字在另外一个数字相邻88个格…目录 1.题目
题目描述
输入格式
输出格式
输入输出样例
说明/提示
2.AC 1.题目
题目描述
一个N \times MN×M的由非负整数构成的数字矩阵你需要在其中取出若干个数字使得取出的任意两个数字不相邻若一个数字在另外一个数字相邻88个格子中的一个即认为这两个数字相邻求取出数字和最大是多少。
输入格式
第1行有一个正整数TT表示了有TT组数据。
对于每一组数据第一行有两个正整数NN和MM表示了数字矩阵为NN行MM列。
接下来NN行每行MM个非负整数描述了这个数字矩阵。
输出格式
TT行每行一个非负整数输出所求得的答案。
输入输出样例
输入 #13
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1输出 #1271
172
99
说明/提示
对于第1组数据取数方式如下
[67] 75 63 10
29 29 [92] 14
[21] 68 71 56
8 67 [91] 25
对于20\%20%的数据N, M≤3N,M≤3
对于40\%40%的数据N,M≤4N,M≤4
对于60\%60%的数据N, M≤5N,M≤5
对于100\%100%的数据N, M≤6,T≤20N,M≤6,T≤20。
2.AC
#include iostream
#include string.h
using namespace std;int n, m, ans;
int a[10][10], v[10][10];
int tx[8] {0,1,1,1,0,-1,-1,-1}, ty[8] {1,1,0,-1,-1,-1,0,1};int f1(int cx,int cy) {v[cx][cy];for (int i 0; i 8; i) {int x cx tx[i];int y cy ty[i];if (x 0 || y 0 || x n || y m) continue;v[x][y];}
}int f2(int cx,int cy) {v[cx][cy]--;for (int i 0; i 8; i) {int x cx tx[i];int y cy ty[i];if (x 0 || y 0 || x n || y m) continue;v[x][y]--;}
}int dfs (int cx, int cy, int sum) {if (cy m) {cx;cy 0;}if (cx n) {ans max(ans,sum);return 0;}dfs(cx,cy1,sum);if (!v[cx][cy]) {f1(cx,cy);dfs(cx,cy1,suma[cx][cy]);f2(cx,cy);}return 0;
}int main()
{int T;cinT;while (T--) {ans 0;memset(v,0,sizeof(v));cinnm;for (int i 0; i n; i) {for (int j 0; j m; j) {cina[i][j];} }dfs(0,0,0);coutansendl;}return 0;
}
