若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1750: 嵌套箱问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,248

题目描述

一个d 维箱(x1,x2,……,xd ) 嵌入另一个d 维箱(y1,y2,……,yd) 是指存在1,2,…,d 的一个排列π,使得 xπ1 < y1 ,  xπ2 < y2 ,…,  xπd < yd 。
(1)证明上述箱嵌套关系具有传递性;
(2)试设计一个有效算法,用于确定一个d维箱是否可嵌入另一个d维箱;
(3)给定由n 个d 维箱组成的集合{B1 ,B2 ,…… ,Bn } ,试设计一个有效算法找出这n 个d维箱中的一个最长嵌套箱序列,并用n和d 描述算法的计算时间复杂性。
给定由n个d维箱,试设计一个有效算法,找出这n个d维箱中的一个最长嵌套箱序列。

输入

输入数据含多个测试数据项。每个测试数据项的第一行中有2 个整数n 和d(n,d≤50),分别表示箱的个数和维数。其后n行每行有d个正整数,表示箱的各维的长度。

输出

对每个测试数据项,输出数据占有两行,第一行是其最长嵌套箱序列的长度,第二行是从小到大排列的最长嵌套箱序列。

样例输入

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9

样例输出

5
3 1 2 4 5
4
7 2 5 6

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist