小 X 和小 Y 来到机房,发现机房门口排了一个长长的队伍。他们走近一看,原来这些人正在为练习中国国粹日本玩法而发愁……
机房门口排了 n 个人,第 i 个人的身高为 hi 。他们想分成若干组一起学习。
每一组同学会坐在机房的同一列中。由于后面的同学可以看到前面严格矮于他的同学的屏幕,从而产生“不正打”行为。因此同一列的同学身高必须单调不增(也就是后面同学的身高必须小于等于前面同学的身高)。
所有同学按照一开始排队的顺序依次进入机房。每位同学可以选择坐在之前某个同学后面,也可以选择坐在某个没有人的列的第一个位置。机房的行数和列数没有限制。
小 X 和小 Y 要帮助他们求出最少可以分多少组一起学习。
第一行一个整数 n 表示总人数。
第二行 n 个整数 h1,h2,...,hn ,表示这些人的身高。
一行一个整数,表示最少组数。
7 6 3 6 1 2 4 5
4
样例中一种可行的分组方案:第 1、3、4 个人分到第 1 组,第 2、5 个人分到第 2 组,第 6 个人分到第 3 组,第 7 个人分到第 4 组。这样一共分了 4 组。
没有更优的方案。
数据范围:
20%的数据,n=2;
70%的数据,n≤1000;
100%的数据,1≤n≤2*10^5 ,0≤hi≤10^9
2017 年武进区第 10 届程序设计比赛试题-小学组 T6