17243번 - Almost-K Increasing Subsequence

수열 a₁, a₂, ... , a_n이 주어진다. 이때, 우리는 이 수열에서 0개 이상의 수를 지워서 새로운 수열 b₁, b₂, ... , b_m을 만들 수 있다. 이때, 수열 b₁, b₂, ... , b_m을 수열 a₁, a₂, ... , a_n의 Subsequence라고 부른다. 예를 들어, 수열 (1,2,4,5)의 Subsequence는 (1), (2, 5), (1, 2, 4, 5) 등이 있다.

우리는 수열 A = a₁, a₂, ... , a_n와 K가 주어질때 수열 A의 Longest Almost-K Increasing Subsequence의 길이를 구하고 싶다. Longest Almost-K Increasing Subsequence란, Almost-K Increasing Subsequence중 가장 길이가 긴 수열을 의미하며, Almost-K Increasing Subsequence는 다음과 같이 정의된다.

• 수열 B = b₁, b₂, ... , b_m이 수열 A의 Subsequence라고 가정하자. 이때, 모든 i = 1, 2, ... , m−1에 대하여, b_i > b_i+1인 i의 개수가 K개 이하인 경우, 수열 B를 수열 A의 Almost-K Increasing Subsequence라고 정의한다.

첫 줄에 n, K(1 ≤ n ≤ 500, 0 ≤ K ≤ n)가 주어진다.

두 번째 줄에 정수 a₁, a₂, ... , a_n(1 ≤ a_i ≤ 10⁹)이 주어진다.

수열 A의 Longest Almost-K Increasing Subsequence의 길이를 출력하라.

첫 번째 예제에서 Almost-0 Increasing Subsequence는 (1, 2, 3, 5), (1, 2, 3, 4)가 존재하며, 모두 길이가 4다.

두번째 예제에서 Almost-1 Increasing Subsequence는 (1, 2, 3, 5, 4) 로, 길이가 5다.