作者存档：edward_mj

【题目】http://wenku.baidu.com/view/079ae6f9aef8941ea76e0599.html

【算法分析】非原创。。。。

首先不考虑字典序，那么就是按r排序，然后贪心取就可以了。

现在考虑字典序。

我们考虑到搞字典序有一个通法，那就是尝试加入某一个点，然后判断结果是否仍可以达到最优，如果是，那么就加进去。否则不加。然后就可以得到一个保证字典序的解了。。。

我们先对data按r排一下序，然后注意到如果一个区间包含另一个区间，那么大区间对判断能否构成最优解必然是没用的。删掉。。。

然后我们就会发现，不只R递增，连L也递增了！

然后设MIS(I,J)表示经过处理以后，第I个区间到第J个区间都可以选用，最多能连成多少个区间。

我们加入一条线段的话，那么就只需要判断是否满足

MIS(pos(preR),pos(L))+MIS(pos(R),pos(nextL))+1==MIS(pos(preR),pos(nextL))就行了。

现在来搞MIS

令right(i)^k=right(right(right(i)))…..(right()出现k次)

那么MIS(i,j)=max(k)   条件：right(i)^k<=j

如果是这样的话，就好搞多了。

我们就像rmq的ST算法一样把right(i)^(2^p)处理出来。

然后从i每次以2^step步长向后走，看什么时候不能走就行了。

因为存在一个性质：

2^0、2^1、2^2、2^3……..2^n

它们能通过每个只用一次的加法组成[1..2^(n+1)-1]这个区间里的任意数。

证明的话很容易，直接把+2^k相当于把二进制的某位数变成1，因为2进制与10进制一一对应，所以必然可以组合成。

纵观所以操作，发现平衡树可以解决。。。于是果断写了SBT。。。

【其它】代码写庛了。。。长达250行

【CODE】

#include #include #include #include using namespace std;
const int N=201111;
const int INF=1000000000;
struct Type{int l,r;}d[N],td[N];
int n,xt,tdn,ans,TOT;
int xl[N+N],lg[N],ansl[N];
int right[N][20];

struct SBTType{
    int tot,root;
    struct PointType{int l,r,s,zz;}tr[N];
   
    void update(int &p){
        if (!p) return;
        tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    }   
   
    void left(int &p){
        int k=tr[p].r;
        tr[p].r=tr[k].l;
        tr[k].l=p;
        update(p);
        update(k);
        p=k;
    }   
   
    void right(int &p){
        int k=tr[p].l;
        tr[p].l=tr[k].r;
        tr[k].r=p;
        update(p);
        update(k);
        p=k;
    }
       
    void repair(int &p){
        if (!p) return;
        bool flag=false;
        if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
          right(p);
          flag=true;
        }   
        if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
            left(tr[p].l);
            right(p);
            flag=true;
        }   
        if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
            left(p);
            flag=true;
        }   
        if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
            right(tr[p].r);
            left(p);
            flag=true;
        }   
        if (flag){
            repair(tr[p].l);
            repair(tr[p].r);
            repair(p);
        }   
    }   
   
    void ins(int &p,int i){
        if (!p){
            p=++tot;
            tr[p].l=0; tr[p].r=0; tr[p].zz=i; update(p);
        }
        else{
            tr[p].s++;
            if (d[tr[p].zz].r                                 else ins(tr[p].l,i);
            repair(p);
        }   
    }   
   
    bool cross(int &p,int l,int r){
        if (!p) return false;
        if (r        if (l>d[tr[p].zz].r) return cross(tr[p].r,l,r);
        return true;
    }
   
    int FindR(int &p,int limit){
        if (!p) return 0;
        if (d[tr[p].zz].r<=limit) return max(d[tr[p].zz].r,FindR(tr[p].r,limit));
        return FindR(tr[p].l,limit);
    }   
   
    int FindL(int &p,int limit){
        if (!p) return INF;
        if (d[tr[p].zz].l>=limit) return min(d[tr[p].zz].l,FindL(tr[p].l,limit));
        return FindL(tr[p].r,limit);
    }   
}sbt;   

void input(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&d[i].l,&d[i].r);
    lg[1]=0;
    for (int i=2;i<=n;i++)
      lg[i]=lg[i-1]+(i==1<}   

int binary(int x){
    int l=1,r=xt,mid;
    while (l        mid=(l+r)/2;
        if (x<=xl[mid]) r=mid;
                   else l=mid+1;
    }   
    return l;
}   

void LiSan(){
    xt=0;
    for (int i=1;i<=n;i++){
        xl[++xt]=d[i].l;
        xl[++xt]=d[i].r;
    }
    sort(xl+1,xl+xt+1);
    int tot=xt; xt=0;
    for (int i=1;i<=tot;i++)
      if (!xt || xl[xt]!=xl[i])
        xl[++xt]=xl[i];
    for (int i=1;i<=n;i++){
        d[i].l=binary(d[i].l);
        d[i].r=binary(d[i].r);
    }   
}   

bool cmp(Type x,Type y){
    if (x.r    if (x.r>y.r) return false;
    if (x.l>y.l) return true;
    return false;
}   

void init(){
    for (int i=1;i<=n;i++) td[i]=d[i];
    sort(td+1,td+1+n,cmp);
    tdn=0;
    for (int i=1;i<=n;i++)
      if (!tdn || td[i].l>td[tdn].l)
        td[++tdn]=td[i];
}

void getans(){
    ans=1; int R=td[1].r;
    for (int i=2;i<=tdn;i++)
      if (td[i].l>R){
          ans++;
          R=td[i].r;
      }   
}   

void make_right(){
    for (int k=0;1<    for (int i=1;i<=tdn;i++){
        int l=i+1,r=tdn,mid;
        while (l            mid=(l+r)/2;
            if (td[i].r                              else l=mid+1;
        }   
        if (l>tdn || td[i].r>=td[l].l) right[i][0]=tdn+1;
                                  else right[i][0]=l;
    }   
    for (int k=1;1<      for (int i=1;i<=n;i++)
        right[i][k]=right[right[i][k-1]][k-1];
}  

int MIS(int l,int r){
    if (r    int res=1;
    for (int cur=l,step=lg[r-l+1];step>=0;step–)
      if (right[cur][step]<=r){
          res+=1<          cur=right[cur][step];
      }   
    return res;
}  

int Findmax(int x){
    int l=1,r=tdn,mid;
    while (l        mid=(l+r)/2;
        if (td[mid].l>x) r=mid;
                    else l=mid+1;
    }   
    if (td[l].l>x) return l;
    return INF;
}

int Findmin(int x){
    int l=1,r=tdn,mid;
    while (l+1        mid=(l+r)/2;
        if (td[mid].r                    else r=mid-1;
    }   
    if (td[r].r    if (td[l].r    return -INF;
}   

bool Can(int i){
    if (sbt.cross(sbt.root,d[i].l,d[i].r)) return false;
    int L,R,l,r,tmp1=0,tmp2=0;
    L=sbt.FindR(sbt.root,d[i].l-1);
    R=sbt.FindL(sbt.root,d[i].r+1);
    if (!L) L=1;       else L=Findmax(L);
    if (R==INF) R=tdn; else R=Findmin(R);
    l=Findmin(d[i].l);
    r=Findmax(d[i].r);
    tmp1=MIS(L,l);
    tmp2=MIS(r,R);
    if (tmp1+tmp2+1!=MIS(L,R)) return false;
    return true;
}   

void work(){
    for (int i=1;i<=n;i++)
      if (Can(i)){
        sbt.ins(sbt.root,i);
        ansl[++TOT]=i;
      }   
    printf("%dn",ans);
    for (int i=1;i<=ans;i++){
        printf("%d",ansl[i]);
        if (i!=ans) printf(" ");
    }   
    printf("n");
}   

int main(){
    freopen("convention.in","r",stdin);
    freopen("convention.out","w",stdout);
    input();
    LiSan();
    init();
    getans();
    make_right();
    work();
}   

【算法分析】

这个要想想。。。

首先我们注意到，必然有一条竖线或者横线把3个矩形分成一边一个，一边两个的情况，于是预处理，然后再分类讨论即可。。。

【CODE】

#include #include #include const int N=1511;
int m,n,k;
int w[N][N],sum[N][N],lu1[N][N],rd1[N][N];
int ru1[N][N],ld1[N][N],lu2m[N],lu2n[N],rd21[N],rd22[N];

inline int max(int x,int y){
       if (x>y) return x;
       return y;
}

void input(){
     scanf("%d%d%d",&m,&n,&k);
     int i,j;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++) scanf("%d",&w[i][j]);
     memset(rd21,200,sizeof(rd21));
     memset(lu2m,200,sizeof(lu2m));
     memset(rd22,200,sizeof(rd22));
     memset(lu2n,200,sizeof(lu2n));
     memset(lu1,200,sizeof(lu1));
     memset(rd1,200,sizeof(rd1));
     memset(ld1,200,sizeof(ld1));
     memset(ru1,200,sizeof(ru1));
}

void change(){
     int i,j;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++)
         sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+w[i][j];
     m=m-k+1; n=n-k+1;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++)
         w[i][j]=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];
}

void init(){
     int i,j;
     for (i=1;i<=m;i++)
       for (j=1;j<=n;j++){
           lu1[i][j]=max(lu1[i-1][j],lu1[i][j-1]);
           lu1[i][j]=max(lu1[i][j],w[i][j]);
       }
     for (i=m;i>=1;i–)
       for (j=n;j>=1;j–){
           rd1[i][j]=max(rd1[i+1][j],rd1[i][j+1]);
           rd1[i][j]=max(rd1[i][j],w[i][j]);
       }
     for (i=1;i<=m;i++)
       for (j=n;j>=1;j–){
           ru1[i][j]=max(ru1[i-1][j],ru1[i][j+1]);
           ru1[i][j]=max(ru1[i][j],w[i][j]);
       }
     for (i=m;i>=1;i–)
       for (j=1;j<=n;j++){
           ld1[i][j]=max(ld1[i+1][j],ld1[i][j-1]);
           ld1[i][j]=max(ld1[i][j],w[i][j]);
       }
//处理lu
     for (j=1;j<=n;j++){
         int &t=lu2m[j];
         t=lu2m[j-1];
         for (i=1;i<=m;i++){
           if (i>k) t=max(t,lu1[i-k][j]+w[i][j]);
           if (j>k) t=max(t,lu1[m][j-k]+w[i][j]);
           if (i+k<=m) t=max(t,ld1[i+k][j]+w[i][j]);
         }
     }
     for (i=1;i<=m;i++){
         int &t=lu2n[i];
         t=lu2n[i-1];
         for (j=1;j<=n;j++){        
           if (j>k) t=max(t,lu1[i][j-k]+w[i][j]);
           if (i>k) t=max(t,lu1[i-k][n]+w[i][j]);
           if (j+k<=n) t=max(t,ru1[i][j+k]+w[i][j]);
         }
     }
//处理rd
     for (j=n;j>=1;j–){
         int &t=rd21[j];
         t=rd21[j+1];
         for (i=1;i<=m;i++){
             if (i>k) t=max(t,ru1[i-k][j]+w[i][j]);
             if (j+k<=n) t=max(t,rd1[1][j+k]+w[i][j]);
             if (i+k<=m) t=max(t,rd1[i+k][j]+w[i][j]);
         }
     }
     for (i=m;i>=1;i–){
         int &t=rd22[i];
         t=rd22[i+1];
         for (j=1;j<=n;j++){
             if (j+k<=n) t=max(t,rd1[i][j+k]+w[i][j]);
             if (i+k<=m) t=max(t,rd1[i+k][1]+w[i][j]);
             if (j>k) t=max(t,ld1[i][j-k]+w[i][j]);
         }
     }
}

void work(){
     int ans=0,i,j;
     for (i=1;i+k<=m;i++){
         ans=max(ans,lu1[i][n]+rd22[i+k]);
         ans=max(ans,lu2n[i]+rd1[i+k][1]);
     }
     for (j=1;j+k<=n;j++){
         ans=max(ans,lu1[m][j]+rd21[j+k]);
         ans=max(ans,lu2m[j]+rd1[1][j+k]);
     }
     printf("%dn",ans);
}

int main(){
    freopen("oil.in","r",stdin);
    freopen("oil.out","w",stdout);
    input();
    change();
    init();
    work();
}