bzoj1109 [POI2007]堆積木Klo dp

Description

　Mary在她的生日禮物中有一些積木。那些積木都是相同大小的立方體。每個積木上面都有一個數。Mary用他的

所有積木壘了一個高塔。媽媽告訴Mary遊戲的目的是建一個塔，使得最多的積木在正确的位置。一個上面寫有數i

的積木的正确位置是這個塔從下往上數第i個位置。Mary決定從現有的高塔中移走一些，使得有最多的積木在正确

的位置。請你告訴Mary她應該移走哪些積木。

1<=n<=100000,1<=ai<=1000000

Solution

題意不會複述，幹脆直接貼上來

容易發現一個a[i]能接在a[j]後面需要滿足 j<i j < i 且 aj<ai a j < a i 且 ai−aj≤i−j a i − a j ≤ i − j

把第三個柿子劃一下得到 i−ai≥j−aj i − a i ≥ j − a j ，我們把序列按照柿子③排序，按照柿子②做最長不下降子序列，不難發現這樣得出的答案一定是滿足柿子①的

這就做完了

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

const int L=;
const int N=;

struct data {int x,y;} d[N];

int f[N+],s[L+];

bool cmp(data a,data b) {
    return a.x<b.x||a.x==b.x&&a.y<b.y;
}

int main(void) {
    int n; scanf("%d",&n);
    rep(i,,n) {
        int x; scanf("%d",&x);
        d[i].x=i-x;
        d[i].y=x;
    }
    std:: sort(d+,d+n+,cmp);
    fill(s,); s[]=;
    int ans=;
    rep(i,,n) {
        if (d[i].x<) continue;
        f[i]=;
        int l=,r=ans;
        while (l<=r) {
            int mid=(l+r)>>;
            if (s[mid]>=d[i].y) r=mid-;
            else l=mid+;
        }
        f[i]=l;
        if (f[i]>ans) ans=f[i];
        s[f[i]]=std:: min(s[f[i]],d[i].y);
    }
    // rep(i,0,ans) printf("%d\n", s[i]);
    printf("%d\n", ans);
    return ;
}