问题2833--汉诺塔工厂(factory)

2833: 汉诺塔工厂(factory)

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 16
[提交] [状态] [讨论版] [命题人:]

题目描述

因为在家天天颓废,zpy没钱了。于是zpy想了一个办法,开办了一座汉诺塔工厂。
由于资金短缺,zpy只能使用现有的环。工厂里有n个环,每个环有内径ai,外径bi,高度hi。环要符合一些条件才能放置:
塔的外半径从下至上为非递增序列,即下面的环外径不能小于上面的环。
相邻的两个环中上方环的外径要大于下方环的内径(否则就掉下来了qwq)
现在,zpy想知道符合要求的汉诺塔的最大高度

输入

第一行输入n
第2~n+1行输入n个整数ai,bi,hi

输出

输出符合要求的汉诺塔的最大高度

样例输入 Copy

4
1 2 1
1 3 3
4 6 2
5 7 1

样例输出 Copy

4

提示

可以将环3放在环4上得到高度为3的塔,或者将环1放在环2上得到高度为4的塔。
【数据规模和约定】
50%数据   1<=n<=1000
100%数据  1<=n<= 100000  1<ai,bi,ci<=10^9且bi>ai

来源/分类