最近课上在讲深搜本来是想把这道题当成“工作分配”搜索类问题的模版题出给孩子们的但备课时在网上看了一下大家的答案基本都是用贪心做的很少有用到深搜所以想分享一下本人的深搜思路希望能帮到正在看帖子的你。本思路仅供学习参考请勿抄题解原题链接: link.再放一下题干题目描述某城市冬季举办环城 25km 马拉松接力赛每个代表队有 5 人参加比赛比赛要求每个代表队的每名参赛选手只能跑一次一次至少跑 1km 、最多只能跑 10km而且每个选手所跑的公里数必须为整数即接力的地方在整公里处。刘老师作为学校代表队的教练精心选择了 5 名长跑能手进行了训练和测试得到了这 5 名选手尽力连续跑 1km、2km、…、10km 的所用时间。现在他要进行一个合理的安排让每个选手跑合适的公里数使学校代表队跑完 25km 所用的时间最短。根据队员的情况这个最短的时间是惟一的但安排方案可能并不惟一。根据测试情况及一般运动员的情况得知连续跑 1km 要比连续跑 2km 速度快连续跑 2km 又要比连续跑 3km 速度快……也就是说连续跑的路程越长速度越慢当然也有特殊的就是速度不会变慢但是绝不可能变快。输入格式5 行数据分别是 1 到 5 号队员的测试数据每行的 10 个整数表示某一个运动员尽力连续跑 1km 、 2km、…、10km 所用的时间。时间为一个不超过 107 的正整数。输出格式两行第一行是最短的时间第二行是五个数据分别是 1 到 5 号队员各自连续跑的公里数。本题因为数据量很小所以也可以不考虑剪枝以下代码已在洛谷AC。如有错误或不准确之处请在评论区指出讨论。/* 套用工作安排问题的模版进行搜索 区别在于工作安排问题中每个人只能做一件工作 同一件工作无法安排给多个人完成 而本题每个人奔跑的距离是可以相同的比如5个人都怕5km只要合计25km都可以 */#includeiostreamusing namespace std;int a[6][10],v[6],sum0,minn1e9,he0,d[6];voiddfs(int x){if(x6){//一共有5个人所以如果判断到第6个人了代表递归结束if(he25){//5个人的总距离必须是25km才有效if(minnsum){//判断最短时间minnsum;//如果本次搜索情况为最短时间则用v数组记录每个人的奔跑距离/*这里要强调一下 因为本题每个人的本跑距离i是未经过标记的 也就是每个人都可以跑同样的距离(比如每人5km也合理) 这就导致d数组最后一定会存成10 10 10 10 10这样的数据 所以就必须在判断到最小值的情况下把当前的距离再单独存储到v中 */for(int i1;i5;i){v[i]d[i];}}}return;}for(int i1;i10;i){//每个人都可以跑1~10km中的一种suma[x][i];//记录总时间hei;//记录总奔跑距离d[x]i;dfs(x1);//向下深搜sum-a[x][i];//回溯之前的数据he-i;d[x]0;}}intmain(){for(int i1;i5;i){for(int j1;j10;j){cina[i][j];//正常输入每个人跑不同距离的时间}}dfs(1);//从第1个人开始深搜coutminnendl;//输出最短时间for(int i1;i5;i){//输出5个人分别跑了多少kmcoutv[i] ;}return0;}(第一次分享解题思路不太会用博客有操作不当之处还请友好指出)
