- 论坛徽章:
- 0
|
Problem Description
现在假设共有N名歌手和M名评委,歌手编号为1,2…,N,评委编号为1,2..M。歌手歌唱的时间分别为T1,T2,..,TN。评委们需要对歌手进行点评,且每名歌手需要且仅需要一名评委进行点评,每名评委至少要对一名歌手进行点评,且每一位评委只能对连续编号的某些歌手进行点评,点评时间为这些歌手唱歌时间之和。
现在请你来设计一种点评方案,使得评委们的点评时间尽可能的短。评委们的点评时间定义为点评时间最多的那位评委所用掉的时间。
举个例子:假设有5个歌手,3个评委。歌手的歌唱时间依次为:4 5 3 1 2,那么可以这样进行点评: 4 /5 3 1/ 2 ,即第一位评委点评第一位歌手,用时4个单位;第二位评委点评第二,三,四位歌手,用时9个单位;第三位评委点评第五位歌手,用时2个单位;那么该方案的点评时间为9。
当然这并不是最优的方案,最优方案需要你用程序找出。
Input
第一行一个整数T(T<=100),代表共有T组测试数据。
每组测试数据包括两部分:
第一部分:N M 分别代表歌手数和评委数。(1<=M<=N<=500)
第二部分:N个正整数,分别代表歌手的歌唱时间(不大于2000的正整数)。
Output
输出包括T行,每一行为每个测试用例评委们最短的点评时间。
Sample Input
1
5 3
4 5 3 1 2
Sample Output
6
Author
gamegame151 |
|