给定一个长度为 N 的整数序列:A1, A2, · · · , AN。现在你有一次机会,将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长,请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列,子序列中的每个数不小于在它之前的数。
输入第一行包含两个整数 N 和 K。
第二行包含 N 个整数 A1, A2, · · · , AN。
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 ≤ 105,1 ≤ Ai ≤ 106。
第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 |
|
---|---|
C题 | |
D题 | |
E题 | |
F题 | |
G题 | |
H题 | |
I题 | |
J题 |
注意事项:
1. 对于编程题目,要求选手给出的解答完全符合 GNU C/C++ 标准,不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的 API。
2. 代码中允许使用 STL 类库。
3. main 函数结束必须返回 0。
4. 所有依赖的函数必须明确地在源文件中 #include
5. 提交时,注意选择使用C或C++语言。
比赛结束,可以到题集中训练,长期有效,2022年第十三届蓝桥杯大赛软件类省赛C/C++大学A组真题