[第十届蓝桥杯省赛C++B组]组队

题目来源：第十届蓝桥杯省赛C++B组

算法标签：dfs

题目描述：

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

思路：

意思是说我们要从20人里面选出5个人的阵容使得他们总数最大。 显然看不出什么贪心莽夫技巧，那么我们使用dfs暴搜，每个组合更新最大值，最后输出最大值即可。

题目代码：

#include<iostream>using namespace std;int team[20][6];int max_sum;bool st[20];int max(int a,int b){return a>b?a:b;}void dfs(int u,int sum)//u当前选择团队的第几人，sum当前团队总值{ if(u>5){max_sum=max(max_sum,sum);return;}//如果选完了，更新最大值，退出 for(int i=0;i<20;i++)//20人 { if(!st[i])//如果当前人没有被选择 { st[i]=true;//被选 dfs(u+1,sum+team[i][u]); //选下一个人，队伍总值增加当前人的当前号位的值 st[i]=false;//回溯 } }}int main(){ for(int i=0;i<20;i++) for(int j=0;j<6;j++) cin>>team[i][j];//读队伍 dfs(1,0);//从第一个人开始选，当前总和为0 cout<<max_sum; return 0;}#include<iostream>using namespace std;int ans;bool st[21];int map[21][6]={ 0,0,0,0,0,0, 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};inline int max(int a,int b){ return a>b?a:b;}void dfs(int u,int sum){ if(u>5){ ans=max(ans,sum); return ; } for(int i=0;i<20;i++){ if(!st[i]){ st[i]=true; dfs(u+1,sum+map[i][u]); st[i]=false; } }}int main(){ dfs(1,0); cout<<ans<<endl; return 0;}

答案

490