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

@Pelom  October 12, 2021

题意

有$n$个数,可以进行$k$次操作,每次操作可以选择一个区间让每个数$+1$,求最后最长不下降子序列长度

数据范围:$1 \le n \le 10000,1\le k \le 500$

题解

首先明确一个事实:每次操作的区间的右端点一定是$n$
容易证明:这样不会使答案变小,并且如果不这样可能会使答案变小
用$f[i][j]$表示第$i$个数已经被操作了$j$次,当前的答案,状态转移方程为$$f[i][j]=\max f[k][l]+1 \ (k<i,l \le j,S_k​+l \le S_i​+j)$$
可以用二维树状数组来维护$(j,S_i+j)$
并且可以将$f$降至$1$维,即用$f[i]$表示前$i$个数的答案,这是因为树状数组已经维护了$j$的信息
而在进行$dp$的时候,注意枚举$j$的时候应倒序枚举,原因类似于$01$背包,“被操作了$j$次”最多只会发生一次
因为$j$可以为$0$,所以整个数组向后推一个

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10000+10;
const int K=500+10;
const int A=5000+10;
int n,m;
int a[N];
int ans,mx;
int T[K][A+K];
inline int lowbit(int x){
    return x&-x;
}
inline void update(int x,int y,int k){
    for(;x<=m+1;x+=lowbit(x))
        for(int i=y;i<=m+mx;i+=lowbit(i))
            T[x][i]=max(T[x][i],k);
}
inline int query(int x,int y){
    int res=0;
    for(;x;x-=lowbit(x))
        for(int i=y;i;i-=lowbit(i))
            res=max(res,T[x][i]);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        mx=max(mx,a[i]);
    }
    for(int i=1;i<=n;i++)
        for(int j=m;~j;j--){
            int t=query(j+1,j+a[i])+1;
            ans=max(ans,t);
            update(j+1,j+a[i],t);
        }
    printf("%d",ans);
    return 0;
}

添加新评论