中兴捧月杯赛题2

sir_chen

教师家访安排

2010-05-08 输入文件：student.txt    distance.txt
你是小学某班主任，需要安排周六进行家访。于是打电话与家长联系，他们表示虽然比较忙，但还是会为你抽出一点时间。
由于有些家长时间上有冲突，并且一天内不能拜访所有家长，你需要一个程序安排一天的工作，使得你可以拜访最多的家长。注意，如果与某个家长见面，拜访时间不得少于45分钟（M）,否则可能引起家长不满意。另外从一个家长到另外一个家长需要花费一些时间。

Input1:  student.txt
输入包括多个测试数据，每个测试数据开头是一个整数n（1<=n<=40），表示家长总数。接下来n行每行包括三个正整数m、s、t。m表示家长的序号，s、t分别表示该家长空闲时间段的起始时间和终止时间，s小于t。注意两个数字的最后两位表示分钟。
比如1645 表示16时45分
样本如下：
   6
   1   800    1100   
   2   800    900
   3   845    1000
   4   1300  1400
   5   1345  1800
   6   1500  1700

Input2:  distance.txt
第一行为 家长总数
随后为一个二维表格，记录每2个用户之间的距离。第二行和第一列数据为家长顺序编号。其他数据为2个家长之间的距离。
样本如下：
6
0    1    2    3    4      5     6
1    0    1    2    4      3     1
2    1    0    3    5      3     2
3    2    3    0    6      1     3
4    4    5    6    0      4     14
5    3    3    1    4      0     15
6    1    2    3    14    15   0

Output:
拜访的家长总数
拜访的家长的序号和开始结束时间

sir_chen

初次拿到这道题感觉和最大兼容活动安排相似,但又有不同,因为这里每一步选择都会影响到后面的选择,动态规划可能不大好处理,一时也没想到好的办法,所以就发上来了.

litaoye

如果没有距离的限制，直接贪心就可以解。加上了路程的限制，感觉用状态压缩应该可以，n最大不才40么！