问题 R: 反子序列
传统题
1.000s
时间限制
256MB
内存限制
12 提交
9 解决
【题目描述】
题目描述
给定一个长度为 n
的数列：a1,a2,
...,an
，且每个元素都满足 1≤ai≤k
。请找出一个数列，它的每个元素同样不超过 k 且不低于 1，且新数列不是原数列的子序列（所谓子序列，就是原序列中部分元素构成的序列，这些元素在原序列中不必连续）。请输出新序列的最短长度。
输入格式
第一行：两个正整数 n 与 k；
第二行：n 个正整数表示 a1,a2,
...,an
。
输出格式
单个正整数：表示所求数列的最短长度、
数据范围
对于 50% 数据，1≤n≤100
，1≤k≤10
；
对于 100% 数据，1≤n≤105
，1≤k≤10000
；
样例数据
输入:
5 2
2 2 1 1 2
输出:
3
说明:
1,1,1
是最短的满足条件的序列之一，长度为3
输入:
9 3
1 2 3 1 2 3 1 2 3
输出:
4