Problem5334--高校排名 -训练套题T7T4

5334: 高校排名 -训练套题T7T4

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

4. 高校排名(rank.pas)

 

【问题描述】

  现有3个大学:X大学,Y大学,Z大学。每所大学有三个专业:CS(计算机系)EE(电子工程系),FLS(外语系)。三个专业的国际公认排名为:

CS排名:X>Y>ZX>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的最大值是多少?

【输入文件】

 第一行有两个整数NM0<N,M<100

 接下来M行中,第i1<=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

HINT

HJF:

m=2时,问题相当于经典的最长公共子序列问题

 m>2时,扩展到求m个串的最长公共子序列,时间复杂度为O(n^m),此复杂度不不能承受

 

 将学校i看成一个顶点,如果学校i在人员专业上的排名都高于学校j,则添加一条从顶点i到顶点j的有向边,可以得到一个描述学校间优劣关系的图。题目要求的最长学校序列,就相当于要找该图中的一条最长路,可以用floyed算法在O(n^3)时间内求出

Source/Category