洛谷3287 [SCOI2014]方伯伯的玉米田

题意

有 $N$ 个数，可以进行 $K$ 次操作，每次可以选择一个区间，把其中所有数 $+1$ 。求最后最长不降子序列的长度。

$N\le 10000 \ , \ K\le 500$ 。

题解

可以发现，每次选择区间的右端点一定是 $N$ ，否则就可能出现答案减小的情况，而不可能会增加。

用 $f[i][j]$ 表示第 $i$ 个数被操作了 $j$ 次 ，前 $i$ 个数的最优情况。可以得到方程：

$$f[i][j]=\max f[k][l] \ (k < i \ , \ l\le j \ , \ S_i+j\geq S_k+l)$$

如果从左到右依次计算，第一维感觉可以省略掉。用二维树状数组来维护 $(j,S_i+j)$ 这两维，每次查询之前的最大值 $+1$ 就是答案。

因为 $j$ 可能为 $0$ ，所以操作树状数组时 $+1$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,maxh,h[10005],t[5505][505];

inline void upd(int x,int y,int z) { for (;x<=m+maxh;x+=x&-x) for (int i=y;i<=m+1;i+=i&-i) t[x][i]=max(t[x][i],z); }

inline int query(int x,int y)
{
    int ans=0;
    for (;x;x-=x&-x) for (int i=y;i;i-=i&-i) ans=max(ans,t[x][i]);
    return ans;
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) h[i]=read(),maxh=max(maxh,h[i]);
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=m;~j;j--)
        {
            int cur=query(h[i]+j,j+1)+1;
            ans=max(ans,cur);
            upd(h[i]+j,j+1,cur);
        }
    }
    return !printf("%d",ans);
}