3594: [Scoi2014]方伯伯的玉米田

Time Limit:?60 Sec??Memory Limit:?128 MB
Submit:?1399??Solved:?627
[Submit][Status][Discuss]

Description

方伯伯在自己的農田邊散步，他突然發現田里的一排玉米非常的不美。
這排玉米一共有N株，它們的高度參差不齊。
方伯伯認為單調不下降序列很美，所以他決定先把一些玉米拔高，再把破壞美感的玉米拔除掉，使得剩下的玉米的高度構成一個單調不下降序列。
方伯伯可以選擇一個區間，把這個區間的玉米全部拔高1單位高度，他可以進行最多K次這樣的操作。拔玉米則可以隨意選擇一個集合的玉米拔掉。
問能最多剩多少株玉米，來構成一排美麗的玉米。

Input

第1行包含2個整數n，K，分別表示這排玉米的數目以及最多可進行多少次操作。
第2行包含n個整數，第i個數表示這排玉米，從左到右第i株玉米的高度ai。

Output

輸出1個整數，最多剩下的玉米數。

Sample Input

3 1

2 1 3

Sample Output

3

HINT

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

?????? 從貪心的角度，顯然有從i到n整體提高要比i到某個r提高優。因為當提高范圍為r（r!=n）時，無非兩種情況一種是在[r+1，n]存在一個莊稼原來比（I,r]中的某一個使得在r以前長度最大值的點大于或等于，另一種是沒有更大的。那么對于第二種對于答案沒有貢獻，我們從i到n拔高也就沒影響，而當出現第一種時，可能由于多次拔高使得原本可以在[r+1,n]之間可以有貢獻的點失敗了，那么顯然沒有從i到n拔高更優。

?????? 不優化的姿勢呢顯然。

?????? F[i][j]表示第i個位置時（必須使用第i個位置）使用了j次技能的最大長度。所以F[i][j]=max(F[x][y])(x<i,y<j,a[x]<=a[i]+y-j) ===>（x<i,y<j,a[x]+y<=a[i]+j）。顯然對于每次添加，都是現在已有狀態都是滿足x<i。現在我們可以將y與a[x]+y搞成樹狀數組，每次添加都是在左下角矩形中選一個最大值。然后這兩維就可以優化為log2(n)*log2(m+max(a[i]));

總時間復雜度就是O(n*k* log2(n)*log2(m+max(a[i])))。恩，反正過了=-=。

1 #include<cstdio> 2 #include<iostream> 3 #define lowbit(x) (x&(-x)) 4 using namespace std; 5 const int N=10050; 6 int n,m,mx; 7 int a[N]; 8 int c[N][550]; 9 void add(int x,int y,int w){ 10 for(int i=x;i<=mx;i+=lowbit(i)) 11 for(int j=y;j<=m+1;j+=lowbit(j)) 12 c[i][j]=max(w,c[i][j]); 13 } 14 inline int sum(int x,int y){ 15 int ans=0; 16 for(int i=x;i;i-=lowbit(i)) 17 for(int j=y;j;j-=lowbit(j)) 18 ans=max(ans,c[i][j]); 19 return ans; 20 } 21 int f[N][550]; 22 int main(){ 23 scanf("%d%d",&n,&m); 24 for(int i=1;i<=n;i++){scanf("%d",a+i);mx=a[i]>mx?a[i]:mx;} 25 mx+=m; 26 int ans=0; 27 for(int i=1;i<=n;i++){ 28 for(int j=m;j>=0;j--){ 29 f[i][j]=sum(a[i]+j,j+1)+1; 30 // printf("f[%d][%d]=%d\n",i,j,f[i][j]); 31 add(a[i]+j,j+1,f[i][j]); 32 ans=max(ans,f[i][j]); 33 } 34 } 35 printf("%d",ans); 36 } 37 /* 38 3 1 39 2 1 3 40 */

?

轉載于:https://www.cnblogs.com/Troywar/p/7234206.html

總結

以上是生活随笔為你收集整理的bzoj 3594: [Scoi2014]方伯伯的玉米田的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。