2019.03.28 bzoj3594: [Scoi2014]方伯伯的玉米田（二维bit优化dp）

传送门

题意咕咕咕

思路：直接上二维bitbitbit优化dpdpdp即可。

代码：

#include<bits/stdc++.h>
#define N 10005
#define K 5005
using namespace std;
int n,k,a[N],bit[6005][605],len=0,ans=0;
inline long long read(){
    long long ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){
        ans=(ans<<3)+(ans<<1)+ch-'0';
        ch=getchar();
    }
    return ans;
}
inline int lowbit(int x){return x&-x;}
inline void update(int nx,int mx,int v){
    for(int i=nx;i<=len+k;i+=lowbit(i))
        for(int j=mx;j<=k+1;j+=lowbit(j))
            bit[i][j]=max(bit[i][j],v);
}
inline int query(int nx,int mx){
    int ret=0;
    for(int i=nx;i;i-=lowbit(i))
        for(int j=mx;j;j-=lowbit(j))
            ret=max(ret,bit[i][j]);
    return ret;
}
int main(){
    n=read();
    k=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        len=max(a[i],len);
    }
    for(int i=1;i<=n;++i){
        for(int j=k;j>=0;--j){
            int pos=query(a[i]+j,j+1)+1;
            ans=max(ans,pos);
            update(a[i]+j,j+1,pos);
        }
    }
    printf("%d",ans);
    return 0;
}

巴特西

2019.03.28 bzoj3594: [Scoi2014]方伯伯的玉米田（二维bit优化dp）

最新文章

热门文章