P1123 取数游戏

admin

https://www.luogu.org/problemnew/show/P1123

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

输入输出格式
输入格式：
输入第1行有一个正整数T，表示了有T组数据。

对于每一组数据，第1行有两个正整数N和M，表示了数字矩阵为N行M列。

接下来N行，每行M个非负整数，描述了这个数字矩阵。

输出格式：
输出包含T行，每行一个非负整数，输出所求得的答案。

输入输出样例
输入样例#1：
3
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

输出样例#1：
271
172
99
说明
对于第1组数据，取数方式如下：

[67] 75 63 10

29 29 [92] 14

[21] 68 71 56

8 67 [91] 25

对于20%的数据，N, M≤3；

对于40%的数据，N, M≤4；

对于60%的数据，N, M≤5；

对于100%的数据，N, M≤6，T≤20。

黄煦喆

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. #define ri(x,a,b) for(register int x=a;x<=b;x++)
   
5. using namespace std;
   
6. int n,m,t,tx,ty,s;
   
7. int mp[7][7],b[7][7];
   
8. int dx[9]={0,0,1,1,1,0,-1,-1,-1};
   
9. int dy[9]={0,1,-1,0,1,-1,0,-1,1};
   
10. void ch(int x,int y,int sum)
    
11. {
    
12.     if(x>m)s=max(s,sum);
    
13.     else if(y>n)ch(x+1,1,sum);
    
14.     else if(b[x][y])ch(x,y+1,sum);
    
15.     else
    
16.     {
    
17.         ri(i,1,8)
    
18.         {
    
19.             tx=x+dx[i];
    
20.             ty=y+dy[i];
    
21.             b[tx][ty]++;
    
22.         }
    
23.         ch(x,y+1,sum+mp[x][y]);
    
24.         ri(i,1,8)
    
25.         {
    
26.             tx=x+dx[i];
    
27.             ty=y+dy[i];
    
28.             b[tx][ty]--;
    
29.         }
    
30.         ch(x,y+1,sum);
    
31.     }
    
32. }
    
33. int main()
    
34. {
    
35.     //freopen("qu.in","r",stdin);
    
36.     cin>>t;
    
37.     while(t--)
    
38.     {
    
39.         s=0;
    
40.         cin>>m>>n;
    
41.         memset(mp,0,sizeof(mp));
    
42.         memset(b,0,sizeof(b));
    
43.         ri(i,1,m)
    
44.         ri(j,1,n)
    
45.         cin>>mp[i][j];
    
46.         ch(1,1,0);
    
47.         cout<<s<<endl;
    
48.     }
    
49.     return 0;
    
50. }
    

复制代码

lyc

1. #include<iostream>
   
2. #include<algorithm>
   
3. #include<cstring>
   
4. using namespace std;
   
5. int a[10][10];
   
6. int fx[10] = {1,1,1,0,0,-1,-1,-1};
   
7. int fy[10] = {1,0,-1,1,-1,0,1,-1};
   
8. int vis[10][10];
   
9. int ans = 0;
   
10. int n,m;
    
11. void dfs(int x, int y, int sum){
    
12.     int nx = x;
    
13.     int ny = y+1;
    
14.     if(ny == m+1){
    
15.         nx++;
    
16.         ny = 1;
    
17.     }
    
18.     if(x == n+1){
    
19.         ans = max(ans, sum);
    
20.         return ;
    
21.     }
    
22.     if(vis[x][y] == 0){
    
23.     vis[x][y] ++;
    
24.     for(int i=0; i<7; i++)
    
25.         vis[x+fx[i]][y+fy[i]] ++;
    
26.     dfs(nx, ny, sum+a[x][y]);
    
27.     for(int i=0; i<7; i++)
    
28.         vis[x+fx[i]][y+fy[i]] --;
    
29.     vis[x][y] --;
    
30.     }
    
31.     dfs(nx, ny, sum);
    
32. }
    
33. int main(){
    
34.     int t;
    
35.     cin>>t;
    
36.     while(t--){
    
37.         ans = 0;
    
38.         memset(a, 0, sizeof(a));
    
39.         cin>>n>>m;
    
40.         for(int i=1; i<=n; i++)
    
41.             for(int j=1; j<=m; j++)
    
42.             cin>>a[i][j];
    
43.         dfs(1, 1, 0);
    
44.         cout<<ans<<endl;
    
45.     }
    
46.     return 0;
    
47. }
    
48. 
    

复制代码

张笑宇

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,m,ans;
   
4. int a[15][15];
   
5. int dx[9]={0,1,1,1,0,0,-1,-1,-1};
   
6. int dy[9]={0,1,-1,0,-1,1,0,1,-1};
   
7. int can[15][15];
   
8. void DFS(int i,int j,int now)
   
9. {
   
10.     if(j>m)
    
11.         {
    
12.         i++;
    
13.         j=1;
    
14.     }
    
15.     if(i>n)
    
16.         {
    
17.         if(now>ans)ans=now;
    
18.         return;
    
19.     }
    
20.     int k;
    
21.     if(can[i][j]==0){
    
22.         for(k=1;k<9;k++) can[i+dx[k]][j+dy[k]]++;
    
23.         DFS(i,j+2,now+a[i][j]);
    
24.         for(k=1;k<9;k++) can[i+dx[k]][j+dy[k]]--;
    
25.     }
    
26.     DFS(i,j+1,now);
    
27. }
    
28. int main(){
    
29.     int t,i,j;
    
30.     scanf("%d",&t);
    
31.     while(t--){
    
32.         scanf("%d%d",&n,&m);
    
33.         ans=0;
    
34.         for(i=1;i<=n;i++){
    
35.             for(j=1;j<=m;j++)scanf("%d",&a[i][j]);
    
36.         }
    
37.         memset(can,0,sizeof(can));
    
38.         DFS(1,1,0);
    
39.         cout<<ans<<endl;
    
40.     }
    
41.     return 0;
    
42. }{:3_41:}

复制代码

admin

很好！此题有两种做法，一个是DFS，判断某个数字是否可被选，然后比较最大值。
第二种方法是状压DP，大家看看我的DFS程序

1. #include<iostream>
   
2. using namespace std;
   
3. int t,n,m;
   
4. int a[8][8];
   
5. int b[8][8];  ///这个表示i,j位置被几个已选数字控制了！！！！
   
6. int ans;
   
7. int nx[]= {0,-1,-1,-1,+0,+0,+1,+1,+1};
   
8. int ny[]= {0,-1,+0,+1,-1,+1,-1,+0,+1};
   
9. void dfs(int i,int sum)
   
10. {
    
11.     int x,y,tx,ty,k;
    
12.     if(i>n*m)
    
13.     {
    
14.         if(sum>ans) ans=sum;
    
15.     }
    
16.     else
    
17.     {
    
18.         x=(i-1)/m+1,y=(i-1)%m+1;
    
19.         if(b[x][y]) dfs(i+1,sum);
    
20.         else
    
21.         {
    
22.             for( k=1; k<=8; k++)
    
23.             {
    
24.                 tx=x+nx[k],ty=y+ny[k];
    
25.                 if(tx<=n &&ty<=m &&tx>=1 && ty>=1) b[tx][ty]++;
    
26.             }
    
27.             dfs(i+1,sum+a[x][y]);
    
28.             for( k=1; k<=8; k++)
    
29.             {
    
30.                 tx=x+nx[k],ty=y+ny[k];
    
31.                 if(tx<=n &&ty<=m &&tx>=1 && ty>=1) b[tx][ty]--;
    
32.             }
    
33.             dfs(i+1,sum);
    
34.         }
    
35.     }
    
36. }
    
37. int main()
    
38. {
    
39.     cin>>t;
    
40.     while(t--)
    
41.     {
    
42.         ans=-1;
    
43.         cin>>n>>m;
    
44.         for(int i=1; i<=n; i++)
    
45.             for(int j=1; j<=m; j++)
    
46.             {
    
47.                 cin>>a[i][j];
    
48.                 b[i][j]=0;
    
49.             }
    
50.         dfs(1,0);
    
51.         cout<<ans<<endl;
    
52.     }
    
53.     return 0;
    
54. }
    

复制代码