2 flushhip FlushHip 于 2016.04.01 16:03 提问

算法题目,求解,赶时间,在线等! 3C

长跑接力赛全程m公里,规定:每个队5人,每个人都必须而且只能跑一次,并且至少跑1公里、最多跑n公里,接力点必须在整公里处。刘教练挑选了5名队员,测试后得到每个人连续跑1、2、3、……、n公里的最短时间。他准备精心安排每个队员跑的公里数,使全队完成接力赛用时最短。你能帮教练做一个最佳方案吗?(数据保证最佳方案唯一)
(设:每人连续跑的路程越长速度越慢,若有保持速度的,也绝不会变快。)

[输入]m n (m≦5000,n≤1000)
下接5行,每行n个整数(表示每个连续跑1~n公里的最短时间,以空格相隔)

[输出]第一行:最短时间(时间≤maxlongint)
第二行:五个整数(表示安排1-5号队员各自连续跑的公里数,以空格相隔)
[样例]输入:
25 10
333 700 1200 1710 2240 2613 3245 3956 4778 5899
300 610 960 1370 1800 2712 3834 4834 5998 7682
298 612 990 1560 2109 2896 3790 4747 5996 7654
289 577 890 1381 1976 2734 3876 5678 6890 9876
312 633 995 1467 1845 2634 3636 4812 5999 8123
输出:
9748
6 5 5 4 5

2个回答

devmiao
devmiao   Ds   Rxr 2016.04.01 23:13
AIRE_Talent
AIRE_Talent   2016.04.02 00:54

m = 25;
n = 10;
map = [333 700 1200 1710 2240 2613 3245 3956 4778 5899
300 610 960 1370 1800 2712 3834 4834 5998 7682
298 612 990 1560 2109 2896 3790 4747 5996 7654
289 577 890 1381 1976 2734 3876 5678 6890 9876
312 633 995 1467 1845 2634 3636 4812 5999 8123];
a1 = [1 0 0 0 -1]';
a2 = [0 1 0 0 -1]';
a3 = [0 0 1 0 -1]';
a4 = [0 0 0 1 -1]';
f = @(x1,x2,x3,x4)m+a1.*x1+a2.*x2+a3.*x3+a4.*x4;
time = inf;
index = [0 0 0 0 0];
for x1 = 1:n
for x2 = 1:n
for x3 = 1:n
for x4 = 1:n
x5 = m-x1-x2-x3-x4;
if x5>0&x5<=n
t = map(1,x1)+map(2,x2)+map(3,x3)+map(4,x4)+map(5,x5);
if (time>t)
time = t;
index = [x1 x2 x3 x4 x5];
end
end
end
end
end
end
数据量比较小,这样实现是最快的

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
最近公共祖先(LCA):离线&在线算法
Tarjan算法适用于离线批量处理多个查询请求。基本思想是以深度优先搜索的顺序访问这颗树,给这棵树的结点染色,一开始所有结点都是白色的,而当第一次经过某个结点的时候,将它染成灰色,而当第二次经过这个结点的时候——也就是离开这棵子树的时候,将它染成黑色。
算法复习1——暴力法
蛮力法 基于问题的描述和所涉及的概念、定义直接求解,逐一列举并处理问题所涉及的所有情形,而后得到问题的答案。 优点:逻辑清晰,简单,易于实现 缺点:效率不高 适用于规模比较小的问题 基本技术:扫描技术和枚举方法 1.排序问题 (1)选择排序 (2)冒泡排序 2.查找问题 顺序查找 3.字符串匹配问题 //蛮力法求解字符串匹配问题 //输入:文本W[0..n-1]
暴力破解数独+舞蹈链算法解数独
求解数独的思路 我想通过自己的思路来求解,虽然网上肯定有非常巧妙高效的解法。因此我安装了HoDoKu这个软件,这个软件会分析当前数独每个待填格子可能存在的值,目前我发现Naked Or Hiden Single这2中是最容易找出来的,找出来了该位置就必填那个数。下图是一个例子,表示裸露的单个数字,该位置只有一种可能值。经过仔细研究,我得出了2个原则: 1.当前位置只有一种可能值,则优先填入 2
急什么,我们又不赶时间
急什么,我们又不赶时间 我们总是害怕来不及,错过一班地铁会让我们懊恼不已。似乎,走得慢一点,背后就有吃人的怪兽要等着把我们给吞噬掉。在你最该肆无忌惮的时候,你却唯唯诺诺,浪费了人生,也是辜负了青春。在你最该细细品味的时候,你却匆匆忙忙,对不起光阴,也对不起自己。 无聊的刷着微博的时候发现了这段话,觉得写得不错。每次遇到写得不错的语句的时候他总是把它们记下,保存在手机的记事本上。这似乎成了他一个习
2018今日头条算法面试编程题2
点击打开链接给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个:区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可,不需要输出具体的区间。如给定序列  [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值: [6] = 6 * 6 = 36;[2] = 2 * 2 = 4;[1] = 1 * 1 = 1;[6,2] = 2 *...
常用数据挖掘算法 - 决策树ID3&关联推荐Apriori &朴素贝叶斯NBC
数据挖掘主要解决四类问题: 分类:预测主题属于(A,B,C)类,前提预先知道分类,根据构造模型算法将输入数据分类,而非一个具体数值(广义预测)-(决策树,Logistic回归,神经网络) 聚类:把一个对象划分若干组,核心划分依据,如果选择若干指标(成本,价格,质量)对已有体验用户群进行划分,按指标计算距离归类(K-means聚类,聚类分)根据很多特征,相似分为一组。最大化类内相似性,最小化类间相
在线笔试题目解答
 1.a.POINT *p;   b.POINT **p;   c.POINT p[16];   d.POINT **p;   e.POINT *p = new POINT[16];2.    #include iostream>using namespace std;//判断是否为偶数的函数//是偶数,则返回1,否则返回0int isEven(int n)...{ /**//*i
暴力求解法之简单枚举--除法
输入正整数n,按从小到大的顺序输出所有形如abcde/fghij=n的表达式,其中a~j恰好为数字0 ~9 的一个排列,2 样例输入: 62 样例输出: 79546 / 01283 = 62 94736 / 05128 = 62 【分析】 不需要枚举所有的排列,只需要枚举被除数,除数自然可以计算出来 不过由于细节问题,也是搞了挺久,各种磕磕绊绊,还是题目做少了,经验不足,下面贴上两
ACM大学生程序设计竞赛在线题库精选题解 算法分析与设计习题解答
随着各大专院校参加ACM/ICPC热情的高涨,迫切 需要有关介绍ACM国际大学生程序设计竞赛题解的书 籍。赵端阳、吴艳、石洗凡主编的《ACM大学生程序 设计竞赛在线题库精选题解--算法分析与设计习题解 答》是在浙江大学、北京大学和杭州电子科技大学的 在线题库中精选了部分题目进行分析和解答,比较详 细地分析和深入浅出地讲解了解题的方法和用到的算 法。精选的题目算法特征明显、具有代表性,题目类 型包括基础编程与技巧、模拟算法、字符串处理、大 整数运算、数据结构、搜索算法、动态规划算法、贪 心算法、回溯算法、图论算法、几何和数学题。 本书可以作为高等院校有关专业的本科和大专学 生参加国际大学生程序设计竞赛的辅导教材,或者作 为高等院校数据结构、C/C++程序设计或算法设计与 分析等相关课程的教学参考书。 本书的全部源代码,都可以在北京邮电大学出版 社网站下载。
数据结构和算法设计(迷宫求解问题的栈和队列的实现)
此问题中,迷宫用一个二位数组data[ ][ ]表示,data[i][j]的值为0,则表示该点为通路;如果为1,则表示该点为障碍;如果为-1,则表示该点已经走过。数组的四周值都为1,表示边界。给定起点和终点,求起点到终点的路径。 可以使用栈对二维数组进行深度优先搜索,直到找到终