OpenJudge

18:bridging signals----最长升序列(改进算法)

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
10240kB
描述
有一个二分图的完全匹配,二分图两个顶点集合大小相等。现在要从中取定尽量多的边,使得任意两条边都不相交。如下图所示,连接关系是(4, 2, 6, 3, 1, 5),最多取3条边,满足要求。
图片下载:http://u.115.com/file/dnswf78n#
1631_1.jpg
输入
第一行是整数p,p<40000,表示每个集合顶点个数。
接下来的p行,每行一个数,依次表示左边的点与哪一个右边的点连接。
输出
一个整数,表示做多的边数
样例输入
6
4
2
6
3
1
5
样例输出
3
提示
测试数据下载:http://u.115.com/file/clv8z923#
bridging.rar
[样例输入2]
10
2
3
4
5
6
7
8
9
10
1
[样例输出2]
9
[样例输入3]
8
8
7
6
5
4
3
2
1
[样例输出3]
1
[样例输入4]
9
5
8
9
2
3
1
7
4
6
[样例输出4]
4
全局题号
3620
添加于
2011-07-20
提交次数
19
尝试人数
10
通过人数
9