MZ test17# NOIP模拟题 #T3 第3 题 登山机器人(robot.pas/cpp)
第3 题 登山机器人(robot.pas/cpp)
【问题描述】
登山机器人是一个极富挑战性的高技术密集型科学研究项目,它为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。
登山机器人可以携带有限的能量。在登山过程中,登山机器人需要消耗一定能量,连续攀登的路程越长,其攀登的速度就越慢。在对 n 种不同类型的机器人作性能测试时,测定出每个机器人连续攀登1米,2米,…,k米所用的时间。现在要对这n个机器人进行综合性能测试,举行机器人接力攀登演习。攀登的总高度为 m米。规定每个机器人只能攀登 1次或者不攀登,每次至少攀登1米,最多攀登k 米,而且每个机器人攀登的高度必须是整数,即只能在整米处接力。安排每个机器人攀登适当的高度,使完成接力攀登用的时间最短。
编程任务:给定 n 个登山机器人接力攀登的总高度m,以及每个机器人连续攀登 1 米,2 米,…,k米所用的时间,编程计算最优攀登方案。
【输入数据】
第一行是正整数n(1≤n≤1000),k(1≤k≤400)和 m(1≤m≤5000)分别表示机器人的个数,每个机器人最多可以攀登的高度,和攀登的总高度。接下来的 n行中,每行有 k个正整数,分别表示机器人连续攀登1米,2米,…,k 米所用的时间。
【输出数据】
最短攀