广州C/C++培训
达内广州岗顶中心

18087159764

热门课程

纸箱堆叠(1s 128MB) box

  • 时间:2017-01-16
  • 发布:广州C++培训
  • 来源:达内新闻

广州C++培训机构的小编这一期分享纸箱堆叠(1s 128MB) box。

【问题描述】

P工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数n, p, a之后,即可自动化生产三边边长为

(a mod P, a^2 mod p, a^3 mod P)

(a^4 mod p, a^5 mod p, a^6 mod P)

....

(a^(3n-2) mod p, a^(3n-1) mod p, a^(3n) mod p)

的n个纸箱。在运输这些纸箱时,为了节约空间,必须将它们嵌套堆叠起来。

一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。

你的任务是找出这n个纸箱中数量最多的一个子集,使得它们两两之间都可嵌套堆叠起来。

【输入格式】

输入文件的第一行三个整数,分别代表a, p, n

【输出格式】

输出文件仅包含一个整数,代表数量最多的可嵌套堆叠起来的纸箱的个数。

【样例输入】

10 17 4

【样例输出】

2

【样例说明】

生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有(4, 6, 9)可堆叠进(5, 16, 7),故答案为2。

【样例说明】

2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000

题解:

主要算法:CDQ分治(快速排序,树状数组);动态规划(Dp);

我们设长宽高为x,y,z

CDQ分治,以x为关键词排序

接下来递归分成两区间

假设左区间已经处理完了答案

将左右区间分别以y为关键字排序

那么就保证了任何左区间的x必定小于任何右区间的x

我们用两个指针分别从左右区间顺序向后扫

将左区间的z作为位置不断加入树状数组,值为当前点的答案

由于左右区间有序,可以手动保证右区间的扫到的点的y大于所有左区间扫到的点的y

就可以用树状数组更新右区间点的值:当前点的答案等于能转移到当前点的点的答案加一的最大值,这里用上了Dp的思想

然后清空树状数组,再将左右区间合并按第一维排序,恢复原状态,保证处理的是最初的右区间,且此区间按第一维有序

上一篇:广州C++培训机构带你讲SHA-1算法
下一篇:单向链表实现

达内c语言培训班:塔吉特与谷歌携手新零售大亨加入

达内广州c语言培训:苹果联合创始人“不安分”

达内广州c++培训:科技人海战术

达内广州c语言培训:移动网站短时间内提交数据

选择城市和中心
贵州省

广西省

海南省