P5172: 高校排名 -训练套题T7T4
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
4. 高校排名(rank.pas)
【问题描述】
现有
3个大学：
X大学，
Y大学，
Z大学。每所大学有三个专业：
CS(计算机系
)，
EE（电子工程系），
FLS（外语系）。三个专业的国际公认排名为：
CS排名：
X>Y>Z（
X>Y就是说
X大学的
CS专业比
Y大学好）；
EE排名：
X>Z>Y;
FLS排名：
Z>X>Y;
显然，
X大学的每个专业都比
Y大学的好，所以认为
X大学
绝对比
Y大学好。
现在有
N个大学，
M个专业，给出各个大学各个专业的排名情况，我们希望找出一个含若干个大学的有序序列，序列除最后一个大学外，任意一个大学都比他后面的大学要
绝对的好。（参见样例说明）
比如我们找到这样一个序列，
U2>U5>U7>U4,该序列元素个数
K=4。
现要求
K的最大值是多少？
【输入文件】
第一行有两个整数
N和
M（
0<N,M<100）
接下来
M行中，第
i（
1<=i<=M）行有
N个大学的编号，代表第
i个专业的排名，排名越靠前的学校编号，表示该学校的该专业越好。
【输出文件】
一个整数
K。
【样例输入】
4 3
1 2 3 4
1 3 2 4
3 1 2 4
【样例输出】
3
【样例说明】
满足条件的序列有
U1>U2，
U1>U4 ，
U2>U4, U3>U4，
U1>U2>U4，最大值为
3
【提示】
HJF:
当m=2时，问题相当于经典的最长公共子序列问题
当m>2时，扩展到求m个串的最长公共子序列，时间复杂度为O(n^m)，此复杂度不不能承受
将学校i看成一个顶点，如果学校i在人员专业上的排名都高于学校j，则添加一条从顶点i到顶点j的有向边，可以得到一个描述学校间优劣关系的图。题目要求的最长学校序列，就相当于要找该图中的一条最长路，可以用floyed算法在O(n^3)时间内求出