首页 > ACM题库 > HDU-杭电 > hdu 3438 ACM Training待解决[解题报告]C++
2014
03-23

hdu 3438 ACM Training待解决[解题报告]C++

ACM Training

问题描述 :

FZU ACM team launched a series of training courses recently. The training courses lasts exactly N continuous days. There are M lecturers and each day there may be some lecturers talking abort different topics at different time. Each lecturer has a fixed time to make a lecture and the order of the lecturer is fixed. The following is a sample schedule (for example, the first record in the second rows means that daxia has to give a lecture at day 1,4,5 and On “Day 1” there are 4 lecturers making a lecture: daxia at class 1,AekdyCoin at class 4,bluewind at class 6,forza at class 7):
Garden
The training courses are very popular and there are a lot people want to attend the courses. So being the manager of the courses, LL wants to repeat the training courses S times. But as you know, our lecturers are very busy and they want the training finish as early as possible. So could you write a program to calculate the minimum days it needs to finish all the training?Here is a simple example to help you understand the problem:
Garden
There are two lecturers (daxia and yayamao), and the training courses last exactly 2 days.
Now suppose S=2, then one possible schedule may be (Note that schedule here is for all training courses, so here Day 3 is the first day of the second training, i.e.Day 3 is the “Day 1” of second training):
Garden
It cost 4 days in total. But we can do it better, we can rearrange the courses as following:
Garden
Now it only cost 3 days and it’s the best schedule we can achieve.

输入:

In the first line there is an integer T, indicates the number of test cases.(T<=100)
In each case, there is one line contains three integer numbers M,N,S(1<=M<=20, 1<=N<=8,1<=S<=10^6) , indicating the number of the lecturers, the total days of the training course and the repeating times of the training courses. Then following M lines, each line contains N integers of ‘0’ or ‘1’. If the j-th integer is "1" at the i-th line, it means lecturer i should make a lecture on day j.There will be at least one ‘1’ in each case.You should note that the order of the lecturers and the time interval between each lectures should not be changed in each training.
There may be some blank lines between each cases.

输出:

In the first line there is an integer T, indicates the number of test cases.(T<=100)
In each case, there is one line contains three integer numbers M,N,S(1<=M<=20, 1<=N<=8,1<=S<=10^6) , indicating the number of the lecturers, the total days of the training course and the repeating times of the training courses. Then following M lines, each line contains N integers of ‘0’ or ‘1’. If the j-th integer is "1" at the i-th line, it means lecturer i should make a lecture on day j.There will be at least one ‘1’ in each case.You should note that the order of the lecturers and the time interval between each lectures should not be changed in each training.
There may be some blank lines between each cases.

样例输入:

2

2 2 2
1 0
0 1

2 3 2
1 0 1
1 0 0

样例输出:

Case 1: 3
Case 2: 4


  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept