Preparing NOJ

B, 越野赛

5000ms 65536K

Description:

    大戈壁越野赛前后分为很多赛段,一个车队也有多辆车。一个车队在一个赛段只能使用一辆车,但是到达赛段中转站(分隔各赛段的点)时可以任意更换车辆,当然也可以不换。在不同赛段,不同的车有着不同的表现,如果规则不限定换车次数,显然可以在每一个赛段都用最好用的车,但很不幸,换车次数有限定,那么,安排一个合理的换车策略十分重要。我们认为,车队可以选择任意一种车开始赛程,不算换车次数。
    现在依次给出从起点到终点N个赛段中每辆车的表现(跑完当前赛段所需时间),请计算出跑完全部赛程所需最短时间。

Input:

    第一行包含三个正整数N、M、Q,分别表示赛段数、车队用车种类、最大更换车辆次数限制(1≤N≤10000,1≤M≤10,1≤Q≤100)。
    接下来M行,每行N个正整数。第i行第j个数表示i号车在第j赛段的表现(这辆车跑完这个赛段所需时间),每个赛段的时间上限保证不超过1000。

Output:

    输出一行,包含一个整数,表示车队在规则限定内的赛程最短完成时间

Sample Input:

3 2 1
1 4 1
2 2 3

Sample Output:

5

Note:

本题由旧版NOJ导入,来源:ACM爱好者协会

Info

NOJ

Provider NOJ

Code NOJ1859

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet