蓝桥杯:最长不下降子序列

2022-12-07 15:54 743次浏览 0 条评论 C++

给定一个长度为N 的整数序列：A1，A2，…，AN。现在你有一次机会，将其连续的K 个数修改成任意一个相同值。
请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

第一行包含两个整数N和K
第二行包含N个整数A1，A2，…，AN。
20%的测试数据：1≤K≤N≤100；
30%的测试数据：1≤K≤N≤1000；
50%的测试数据：1≤K≤N≤10000；
100%的测试数据：1≤K≤N≤100000，1≤Ai≤10^9。

输出一行包含一个整数表示答案。

5 1
1 4 2 8 5

赞助网站

小码农