华师一附中OI组

标题: P1123 取数游戏 [打印本页]
作者: admin    时间: 2018-5-11 10:50
标题: P1123 取数游戏
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。

作者: 黄煦喆    时间: 2018-5-13 21:53
  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    时间: 2018-5-13 23:20
  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. }

复制代码
作者: 张笑宇    时间: 2018-5-24 22:55
  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    时间: 2018-5-25 17:00
很好！此题有两种做法，一个是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. }
复制代码







欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2