D. 选拔小队

    传统题 1000ms 256MiB

选拔小队

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

训练营要组建一支行进小队,一共安排 nn 个站位,从前到后排成一列。 每个站位都有 kk 名备选队员,每名队员有一个体能分数,同一站位的备选队员分数已经从小到大排好序。现在教练要给每个站位恰好选出一名队员,组成完整小队。 队伍行进时,要求体能严格递增的连续(也就是严格上升子序列)。 教练想知道:我们该如何从每个站位挑选队员,能让这支小队里最长严格递增梯队的长度达到理论最大值,输出这个最大可能长度。

题目描述

给定 nn 个位置,第 ii 个位置提供 kk 个可选数值 ai,1≤ai,2≤⋯≤ai,ka_{i,1}\le a_{i,2}\le \dots \le a_{i,k}。 你需要在每个位置中恰好选取一个数,拼接成长度为 nn 的序列。 求所有能构造出的序列中,最长严格上升子序列(严格 LIS) 的最大可能长度。

输入格式

第一行两个数 k,nk, n,意义如题述。

接下来 nn 行,每行 kk 个数,即 ai,1,ai,2,⋯ ,ai,ka_{ i,1}, a_{i,2},\cdots, a_{i,k}。

输出格式

仅一行一个整数,即所有可能的序列中的最长上升子序列的的最大长度。

样例

2 2
1 3
1 2

2

数据规模与约定

  • 数据点 11:k=1k=1,n≤103n\le 10^3。
  • 数据点 2∼32\sim3:n,k≤100n,k\le 100。
  • 数据点 4∼64\sim6:k≤103k\le 10^3。
  • 数据点 7∼107\sim10:无特殊限制。

对于 100%100\% 的数据,有 1≤k≤5×1031\le k\le 5 \times 10^3,1≤n≤1031 \le n \le 10^3,每个取值都是非负数,不超过 10310^3。

摸底考试

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-7-16 17:15
结束于
2026-10-8 1:15
持续时间
2000 小时
主持人
参赛人数
0