給定一個長度為 N 的整數(shù)序列:A1, A2, · · · , AN。現(xiàn)在你有一次機會,將其中連續(xù)的 K 個數(shù)修改成任意一個相同值。請你計算如何修改可以使修改后的數(shù)列的最長不下降子序列最長,請輸出這個最長的長度。
最長不下降子序列是指序列中的一個子序列,子序列中的每個數(shù)不小于在它之前的數(shù)。
輸入第一行包含兩個整數(shù) N 和 K。
第二行包含 N 個整數(shù) 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、中斷調用、硬件操作或與操作系統(tǒng)相關的 API。
2. 代碼中允許使用 STL 類庫。
3. main 函數(shù)結束必須返回 0。
4. 所有依賴的函數(shù)必須明確地在源文件中 #include
5. 提交時,注意選擇使用C或C++語言。
比賽結束,可以到題集中訓練,長期有效,2022年第十三屆藍橋杯大賽軟件類省賽C/C++大學A組真題