问题 N: 训练法不对
内存限制:512 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:429
解决:100
题目描述
正常来说,一个好的刷题列表应该是循序渐进、每道题都比上一道题难才是合理的。
但是啊,有些佬的刷题单子,虽然每道题都很经典,但是它的难易程度是乱序的!你想想,你带着耳机,坐在实验室,听着音乐哼着歌,突然被乱序刷题单子糊脸了......
大家想一想,对于这样一个题单,把它分成n个子刷题列表,对于每个子刷题列表,所有题的难易顺序保证严格递增。大家觉得合不合适?合适地不得了!
但是,为了最大程度保证刷题单子原本的样子,我们要保证:
但是啊,有些佬的刷题单子,虽然每道题都很经典,但是它的难易程度是乱序的!你想想,你带着耳机,坐在实验室,听着音乐哼着歌,突然被乱序刷题单子糊脸了......
大家想一想,对于这样一个题单,把它分成n个子刷题列表,对于每个子刷题列表,所有题的难易顺序保证严格递增。大家觉得合不合适?合适地不得了!
但是,为了最大程度保证刷题单子原本的样子,我们要保证:
- 每道题只能存在于一个子刷题列表中,并且每道题都至少在一个子刷题列表中出现过。
- 在每一个子刷题列表中,题目的相对顺序保持不变。
- 每个子刷题列表都是非空的
输入
原刷题单子的长度:1≤N≤105
每道题的难易程度:1≤Ai≤109
每道题的难易程度:1≤Ai≤109
输出
最少的子刷题列表的数量
样例输入 复制
5
2
1
4
5
3
样例输出 复制
2
提示
最优解为:
第一组子题单为1题和5题,即2,3
第二组子题单为2题、3题和4题,即1,4,5
因此,总共需要两组子题单。
第一组子题单为1题和5题,即2,3
第二组子题单为2题、3题和4题,即1,4,5
因此,总共需要两组子题单。