蓝桥杯2022年第十三届省赛真题-最长不下降子序列

给定一个长度为 N 的整数序列：A₁, A₂, · · · , A_N。现在你有一次机会，将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。 

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。 

输入第一行包含两个整数 N 和 K。

第二行包含 N 个整数 A₁, A₂, · · · , A_N。 

5 1
1 4 2 8 5

4

对于 20% 的评测用例，1 ≤ K ≤ N ≤ 100；

对于 30% 的评测用例，1 ≤ K ≤ N ≤ 1000；

对于 50% 的评测用例，1 ≤ K ≤ N ≤ 10000；

对于所有评测用例，1 ≤ K ≤ N ≤ 10⁵，1 ≤ A_i ≤ 10⁶。