问题描述
- 算法题目，求解，赶时间，在线等！
-
长跑接力赛全程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
解决方案
http://tieba.baidu.com/p/1614224314
解决方案二：
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
数据量比较小，这样实现是最快的