题目描述

方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，

再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。

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

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

3 12 1 3

输出样例#1：

3

说明

1 < N < 10000，1 < K <= 500，1 <= ai <=5000

 

 

　　首先，需要发现，每次都可以选择拔高至右端点，一定是最贪心的。

　　证明：题目要求的是最后形成最长不下降序列，那么假设我们选择好了左端点，

　　　　　那么为了不让拔高的一段比后面凭空高了那么一截，降低了操作的效果，

　　　　　我们可以将此次操作直接影响到末端。

　　怎么做呢？

　　观察数据范围，可以保存最优子结构再往后传递。

 

　　　　　dp方程：f【i】【j】=max {  f【a】【b】} +1  （a<i, b<=j ,h[a]+b<=h[i]+j）

 

 

　　空间是完全可以承受的。时间方面需要优化。

　　用数据结构的话，肯定不可以带上第三个限制条件，于是就考虑将它去掉。

　　实现方面：直接将 h[a]+b 计入数据结构。

　　最后就是个二维最值的问题了。----------树状数组完全没问题。

 

1 #include
      
        2 using namespace std; 3 int n,m,a,ent; 4 int c[550][5600],ans; 5 void calc_push(int x,int y,int v) 6 { 7     while(x<=m+1) 8     { 9         int tmp=y;10         while(tmp<=5500)11         {12             c[x][tmp]=max(c[x][tmp],v);13             tmp+=tmp&-tmp;14         }15         x+=x&-x;16     }17 }18 void calc_ask(int x,int y,int &pos)19 {20     while(x)21     {22         int tmp=y;23         while(tmp)24         {25             pos=max(pos,c[x][tmp]);26             tmp-=tmp&-tmp;27         }28         x-=x&-x;29     }30 }31 int main()32 {33     scanf("%d%d",&n,&m);34     for(int i=1;i<=n;++i)35     {36         scanf("%d",&a);37         for(int j=m;j>=0;--j)38         {39             calc_ask(j+1,a+j,ent=0);40             calc_push(j+1,a+j,ent+=1);41             ans=max(ans,ent);42         }43     }44     printf("%d",ans);45     return 0;46 }