问题4377--接力马拉松4377: 接力马拉松
时间限制: 1 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
某城市冬季举办环城s km马拉松接力赛，每个代表队有n人参加比赛，比赛要求每名参赛选手只能跑一次，一次至少跑1 km、最多只能跑m km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。
刘老师作为学校代表队的教练，进行了训练和测试，得到了这n名选手尽力连续跑1km、2km、…、m km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完s km所用的时间最短。根据队员的情况，这个最短的时间是唯一的，但安排方案可能并不唯一。
根据测试得知，连续跑的路程越长，花费的时间越多。
输入
第一行s n m
接下有n行，每行有m个数据，分别表示1到n号队员的测试数据，每行的m个整数，表示某一个运动员尽力连续跑1km、2km、…、m km所用的时间。
输出
一行，表示最短的时间。
样例输入
(1)
4 2 3
2 3 4
3 5 6
(2)
25 5 10
333 700 1200 1710 2240 2770 3345 3956 4778 5899
300 610 960 1370 1800 2712 3734 4834 5998 7682
298 612 990 1540 2109 2896 3790 4747 5996 7654
289 577 890 1381 1976 2734 3876 5378 6890 9876
312 633 995 1407 1845 2634 3636 4812 5999 8123
样例输出
(1)
7
【样例说明1】
第一个人跑3 Km, 用时4， 第二个人跑1 km， 用时3， 一共用时7。
(2)
9905
来源/分类
[提交] [状态]