[SCOI2014]方伯伯的玉米田

NC20299. [SCOI2014]方伯伯的玉米田

描述

方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。

方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。

方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。

拔玉米则可以随意选择一个集合的玉米拔掉。问能最多剩多少株玉米，来构成一排美丽的玉米。

输入描述

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

输出描述

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

示例1

输入:

3 1
2 1 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 412ms, 内存消耗: 11384K, 提交时间: 2020-08-14 11:23:21

#include<bits/stdc++.h>
#define lowbit(i) (i&(-i))
using namespace std;
int n,k,l1,l2,a[10001],c[5501][502];
void up(int x,int y,int v){
	for(int i=x;i<=l1;i+=lowbit(i))
		for(int j=y;j<=l2;j+=lowbit(j))
			c[i][j]=max(c[i][j],v);
}int ask(int x,int y){
	int ans=0;
	for(int i=x;i;i-=lowbit(i))
		for(int j=y;j;j-=lowbit(j))
			ans=max(ans,c[i][j]);
	return ans;
}int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",a+i);
		l1=max(l1,a[i]);
	}l1+=k,l2=k+1;
	for(int i=0;i<n;i++)
		for(int j=k;j>=0;j--)
			up(a[i]+j,j+1,ask(a[i]+j,j+1)+1);
	return printf("%d",ask(l1,l2)),0;
}