选拔小队
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
训练营要组建一支行进小队,一共安排 个站位,从前到后排成一列。 每个站位都有 名备选队员,每名队员有一个体能分数,同一站位的备选队员分数已经从小到大排好序。现在教练要给每个站位恰好选出一名队员,组成完整小队。 队伍行进时,要求体能严格递增的连续(也就是严格上升子序列)。 教练想知道:我们该如何从每个站位挑选队员,能让这支小队里最长严格递增梯队的长度达到理论最大值,输出这个最大可能长度。
题目描述
给定 个位置,第 个位置提供 个可选数值 。 你需要在每个位置中恰好选取一个数,拼接成长度为 的序列。 求所有能构造出的序列中,最长严格上升子序列(严格 LIS) 的最大可能长度。
输入格式
第一行两个数 ,意义如题述。
接下来 行,每行 个数,即 。
输出格式
仅一行一个整数,即所有可能的序列中的最长上升子序列的的最大长度。
样例
2 2
1 3
1 2
2
数据规模与约定
- 数据点 :,。
- 数据点 :。
- 数据点 :。
- 数据点 :无特殊限制。
对于 的数据,有 ,,每个取值都是非负数,不超过 。