[数据结构与算法]2022.03.31蓝桥杯第十届 1.分组（dfs）

• 【问题描述】 作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员， 组成球队的首发阵容。 每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1号位至 5 号位的评分之和最大可能是多少？
  

• 数据：
  1 97 90 0 0 0
  2 92 85 96 0 0
  3 0 0 0 0 93
  4 0 0 0 80 86
  5 89 83 97 0 0
  6 82 86 0 0 0
  7 0 0 0 87 90
  8 0 97 96 0 0
  9 0 0 89 0 0
  10 95 99 0 0 0
  11 0 0 96 97 0
  12 0 0 0 93 98
  13 94 91 0 0 0
  14 0 83 87 0 0
  15 0 0 98 97 98
  16 0 0 0 93 86
  17 98 83 99 98 81
  18 93 87 92 96 98
  19 0 0 0 89 92
  20 0 99 96 95 81

• 分析
  用深搜
  按列来
  对每列枚举试着选一行

#include<bits/stdc++.h>
using namespace std;
int mp[20][6];
int vis[20];
int sum=0,ans=0;;
void dfs(int c){
    if(c==6){
        ans=max(ans,sum);
        return;
    }
	for(int i=0;i<20;++i){
        if(!vis[i]){
            vis[i]=true;
            sum+=mp[i][c];
            dfs(c+1);
            sum-=mp[i][c];
            vis[i]=false;
        }
	}
}
int main(){
	for(int i=0;i<20;++i){
        for(int j=0;j<6;++j){
            cin>>mp[i][j];
        }
	}
	dfs(1);//从第一列开始
	cout<<ans<<endl;
	return 0;
}