题目描述

方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。这排玉米一共有$N$株,它们的高度参差不齐。
方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间,把这个区间的玉米全部拔高$1$单位高度,他可以进行最多$K$次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米,来构成一排美丽的玉米。

输入格式

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

输出格式

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

题解

有一个显而易见的贪心:即每次都是拔高以$n$结尾的一段区间是最优的

如果拔高了区间$[i,j]$,其中$j<n$,那么换成拔高$[i,n]$一定不会让答案变得更劣

所以现在的问题就变成每次选择一段后缀上的玉米进行拔高

设$dp[i][j]$表示第$i$株玉米总计被拔高了$j$次时,以第$i$株玉米结尾的最长不降子序列的长度(这个子状态有亿点点难想到)

转移方程:$dp[i][j]=\max(dp[k][l])+1$,其中$k<i,\ l\le j,\ a_k+l\le a_i+j$

那这个max怎么快速求得呢?似乎要用树套树 不过这题由于空间够用,所以树状数组套树状数组就行了

答案就是整个dp数组中的最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define N 10005
#define lowbit(x) x&(-x)
using namespace std;

template <typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

int n, k, a[N], dp[N][505];
int tr[N][505], ans;

void Update(int x, int y, int v) {
y++;
for (int i = x; i <= 10000; i += lowbit(i)) {
for (int j = y; j <= 501; j += lowbit(j)) {
tr[i][j] = max(tr[i][j], v);
}
}
}

int Query(int x, int y) {
y++; int ret = 0;
for (int i = x; i; i -= lowbit(i)) {
for (int j = y; j; j -= lowbit(j)) {
ret = max(ret, tr[i][j]);
}
}
return ret;
}

int main() {
read(n); read(k);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = k; j >= 0; j--) {
dp[i][j] = Query(a[i] + j, j) + 1;
Update(a[i] + j, j, dp[i][j]);
ans = max(ans, dp[i][j]);
}
}
printf("%d\n", ans);
return 0;
}

评论