BZOJ3594【SCOI2014】方伯伯的玉米田 <树状数组优化DP>

Problem

【SCOI2014】方伯伯的玉米田

$\mathrm{Time\;Limit:\;60\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

Input

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

Output

输出$1$个整数，最多剩下的玉米数。

Sample Input

3 1
2 1 3

Sample Output

3

Hint

$1<N<10^4,\;1<K\le500,\;1\le a_i\le5000$

标签：DP 树状数组

Solution

首先，显然每次拔高时，不管从哪里开始拔，区间右边界总是$N$肯定不会使答案变小。有此贪心后，考虑到第$i$株时前面拔高$j$次，那么第$i$株一定也已拔高$j$次。

令$f[i][j]$表示考虑前$i$株，共拔高了$j$次，最多可以剩下多少。那么有

$$f[i][j]=\max{f[p][q]}+1\;\;\;\;(p<i,\;q\le j,\;a[p]+q\le a[i]+j)$$

对于$\mathrm{DP}$值$f[x][y]$，将其坐标设为$(x,a[x]+y)$，那么$\mathrm{DP}$到$f[i][j]$时，需要找的是坐标在$(0,0)\sim(j,a[i]+j-1)$范围内的最小值，可以二维树状数组维护。

注意$\mathrm{DP}$时第二层循环要倒着循环，以排除后效性，由于二维树状数组的坐标范围不能到$0$，可以把所有坐标的横纵值强行加$1$。

Code

#include <bits/stdc++.h>
#define MAX_N 10000
#define MAX_A 5500
#define MAX_M 500
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, a[MAX_N+5], tr[MAX_M+5][MAX_A+5];
void modify(int p, int q, int c) {
    for (int i = p; i <= MAX_M+1; i += (i&-i))
        for (int j = q; j <= MAX_A; j += (j&-j))
            tr[i][j] = max(tr[i][j], c);
}
int query(int p, int q) {
    int ret = 0;
    for (int i = p; i; i -= (i&-i))
        for (int j = q; j; j -= (j&-j))
            ret = max(ret, tr[i][j]);
    return ret;
}
int main() {
    read(n), read(m);	int f, ans = 0;
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++) for (int j = m; ~j; j--)
        ans = max(ans, f = query(j+1, a[i]+j)+1), modify(j+1, a[i]+j, f);
    return printf("%d\n", ans), 0;
}