#P3594. [Scoi2014]方伯伯的玉米田

    ID: 2801 传统题 6000ms 128MiB 尝试: 2124 已通过: 776 难度: 7 上传者: 标签>难度分类提高+/省选-贪心支配关系排序与序列处理最长上升子序列动态规划线性 DP数据结构二维树状数组CF2200数据结构优化DP

[Scoi2014]方伯伯的玉米田

[SCOI2014] 方伯伯的玉米田

题目描述

方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。这排玉米一共有 NN 株,它们的高度参差不齐。方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。每次拔高时,他选择一段连续的玉米,并将其中每株都拔高 11。拔高最多做 KK 次。拔高结束后,他可以拔除任意一些玉米;保留下来的玉米仍按原顺序排列。问能最多剩多少株玉米,来构成一排美丽的玉米。

输入格式

第一行包含两个整数 n,Kn, K,分别表示这排玉米的数目以及最多可进行多少次操作。第二行包含 nn 个整数,第 ii 个数表示这排玉米,从左到右第 ii 株玉米的高度 aia_i。

输出格式

输出一个整数,最多剩下的玉米数。

样例 #1

3 1
2 1 3
3

数据范围

本题采用的范围:2≤N<1042\le N<10^4,1≤K≤5001\le K\le500(含样例中的 K=1K=1),1≤ai≤50001 \leq a_i \leq 5000。