题面
作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，组成球队的首发阵容。
每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少？
题解
DFS，枚举，回溯
枚举五个位置上分别放那个运动员即可，具体见代码。
答案：
490
代码
#include<bits/stdc++.h>
using namespace std;
bool v[20];
int m = 20, n = 5, s; //s为当前最大评分和
int a[20][5] = {
{97, 90, 0, 0, 0},
{92, 85, 96, 0, 0},
{0, 0, 0, 0, 93},
{0, 0, 0, 80, 86},
{89, 83, 97, 0, 0},
{82, 86, 0, 0, 0},
{0, 0, 0, 87, 90},
{0, 97, 96, 0, 0},
{0, 0, 89, 0, 0},
{95, 99, 0, 0, 0},
{0, 0, 96, 97, 0},
{0, 0, 0, 93, 98},
{94, 91, 0, 0, 0},
{0, 83, 87, 0, 0},
{0, 0, 98, 97, 98},
{0, 0, 0, 93, 86},
{98, 83, 99, 98, 81},
{93, 87, 92, 96, 98},
{0, 0, 0, 89, 92},
{0, 99, 96, 95, 81}
};
void dfs(int u, int c) { //当前枚举到第 u 个位置，总共评分为 c
if (u == n) { //枚举完五个位置，更新答案，退出递归
s = max(s, c);
return;
}
for (int i = 0; i < m; i++) { //判断每个远动员是否在前几个位置中被使用了
if (v[i]) continue; //用过，不能再使用
v[i] = true; //标记为使用过
dfs(u + 1, c + a[i][u]);
v[i] = false; //回溯，恢复现场
}
}
int main() {
dfs(0, 0); //从第0个位置开始枚举
cout << s << endl;
return 0;
}
| 标题： | 2019年第十届蓝桥杯省赛-A.组队 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/211 |
| 更新： | 2022-09-18 22:48:35 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |