题目
Description
方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。
这排玉米一共有N株，它们的高度参差不齐。
方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米，来构成一排美丽的玉米。
第1行包含2个整数n，K，分别表示这排玉米的数目以及最多可进行多少次操作。
第2行包含n个整数，第i个数表示这排玉米，从左到右第i株玉米的高度ai。
Output
输出1个整数，最多剩下的玉米数。
Sample Output
HINT
1 < N < 10000，1 < K ≤ 500，1 ≤ ai ≤5000
题解
我最恨的就是DP了！！！
不过为了讲课还是做了一下，毕竟tkys_Austin大佬都推荐了。
首先，通过思考我们可以得出每次操作区间的右端点一定为n，否则后面赫鲁晓夫玉米的高度相对前面的高度就会减少，被拔的也就会变多，不满足最优
我们可以以DP[i][j]表示被操作j次后以i为右端点的最长不下降子序列长度，显然，i被操作了j次，高度就为Orig[i]+j
根据这些我们就能得出状态转移方程： 1
| dp[i][j]=max{dp[k][p]+1}, a[k]+p≤a[i]+j, p≤j, k<i
|
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
| #include<cstdio>
#define MAX(a, b) a > b ? a : b
using namespace std;
int f(-1);
inline char GetCharacter() {
static char buf[2000000], *p1 = buf, *p2 = buf;
return (p1 == p2) &&
(p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ?
EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
f = 1, x = 0;
static char c = GetCharacter();
while (!IS_DIGIT(c)) {
if (c == '-') f = -1;
c = GetCharacter();
}
while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
x *= f;
}
#undef IS_DIGIT
int n,K;
int origin[10010];
int dp[10010][510];
int main(int argc, char **argv) {
Read(n), Read(K);
for (register int i(1); i <= n; ++i) Read(origin[i]);
for (register int i(1); i <= n; ++i) {
for (register int j(K); j >= 0; --j) {
for (register int x(0); x < i; ++x) {
for (register int y(K); y >= 0; --y) {
if (origin[x] + y <= origin[i] + j) {
dp[i][j] = MAX(dp[i][j], dp[x][y] + 1);
}
}
}
}
}
printf("%d\n", dp[n][K]);
return 0;
}
|
亲身体验之后完美爆零
因为这样的时间复杂度是 \(\Theta(n^{2}k^{2})\) ，直接爆炸
怎么办呢？我们可以用二维树状数组优化
二维树状数组写法差不多，只是多了一重循环。基本思想不变，时间复杂度被优化到了\(\Theta(nklgnlgk)\) ，就AC了
代码 code
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<cstdio>
#define MAX(a, b) a > b ? a : b
using namespace std;
int f(-1);
inline char GetCharacter() {
static char buf[2000000], *p1 = buf, *p2 = buf;
return (p1 == p2) &&
(p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ?
EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
f = 1, x = 0;
static char c = GetCharacter();
while (!IS_DIGIT(c)) {
if (c == '-') f = -1;
c = GetCharacter();
}
while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
x *= f;
}
#undef IS_DIGIT
int origin[10010], fenwick_tree[10010][510];
int n, K, max_original_height, sum, ans;
#define LOWBIT(i) ((i)&(-i))
inline void Update(register int index1, register int index2, const int &delta) {
register int index(index2);
while (index1 <= max_original_height + K) {
index2 = index;
while (index2 <= K + 1) {
fenwick_tree[index1][index2] = MAX(fenwick_tree[index1][index2],
delta);
index2 += LOWBIT(index2);
}
index1 += LOWBIT(index1);
}
}
inline int GetSum(register int index1, register int index2){
register int ret(0), index(index2);
while (index1) {
index2 = index;
while (index2){
ret = MAX(ret, fenwick_tree[index1][index2]);
index2 -= LOWBIT(index2);
}
index1 -= LOWBIT(index1);
}
return ret;
}
#undef LOWBIT
int main(int argc, char **argv){
Read(n), Read(K);
for (register int i(1); i <= n; ++i) Read(origin[i]),
max_original_height = MAX(max_original_height, origin[i]);
for (register int i(1); i <= n; ++i) {
for (register int j(K); j >= 0; --j) {
sum = GetSum(origin[i] + j, j + 1) + 1;
Update(origin[i] + j, j + 1, sum);
ans = MAX(ans, sum);
}
}
printf("%d\n", ans);
return 0;
}
|