BZOJ3532 : [Sdoi2014]Lis

时间：2021-10-22 12:59:38

f[i]表示以i为结尾的LIS长度

对于所有f[i]=1的，由S向i连边

对于所有f[i]=maxf的，由i向T连边

对于j<i,a[j]<a[i],且f[j]+1=f[i]的，j向i连边

将每个点拆点求最小割

对于字典序最小，

按C从小到大排序，

对于C第i小的点，将b减去$2^{-i}$

最后最小总代价为最大流的整数部分+1

方案的二进制表示为1-最大流的小数部分

用高精度二进制，压62位

#include<cstdio>

#include<algorithm>

typedef long long ll;

const int N=1410,BIT=12;

const ll MOD=(1LL<<62)-1;

struct Num{

  int x;ll ex[BIT];

  Num(){for(int i=x=0;i<BIT;i++)ex[i]=0;}

  Num(int _x){

    for(int i=0;i<BIT;i++)ex[i]=0;

    x=_x;

  }

  Num(int _x,int y){

    for(int i=0;i<BIT;i++)ex[i]=0;

    x=_x;

    ex[y/62]=1LL<<(61-y%62);

  }

  Num operator+(Num b){

    Num c;

    c.x=x+b.x;

    for(int i=0;i<BIT;i++)c.ex[i]=ex[i]+b.ex[i];

    for(int i=BIT-1;i;i--)if(c.ex[i]>MOD)c.ex[i-1]++,c.ex[i]&=MOD;

    if(c.ex[0]>MOD)c.x++,c.ex[0]&=MOD;

    return c;

  }

  Num operator-(Num b){

    Num c;

    c.x=x-b.x;

    for(int i=0;i<BIT;i++)c.ex[i]=ex[i]-b.ex[i];

    for(int i=BIT-1;i;i--)if(c.ex[i]<0)c.ex[i-1]--,c.ex[i]+=MOD+1;

    if(c.ex[0]<0)c.x--,c.ex[0]+=MOD+1;

    return c;

  }

  void operator+=(Num b){*this=*this+b;}

  void operator-=(Num b){*this=*this-b;}

  bool operator<(Num b){

    if(x!=b.x)return x<b.x;

    for(int i=0;i<BIT;i++)if(ex[i]!=b.ex[i])return ex[i]<b.ex[i];

    return 0;

  }

  bool operator==(Num b){

    if(x!=b.x)return 0;

    for(int i=0;i<BIT;i++)if(ex[i]!=b.ex[i])return 0;

    return 1;

  }

}inf,maxflow,zero,tmp;

int Test,n,i,j,S,T,h[N],gap[N],f[N],maxf,cnt,flag;

struct edge{int t;Num f;edge *nxt,*pair;}*g[N],*d[N];

struct Point{int a,b,c,id;bool del;}val[N];

bool cmp1(Point a,Point b){return a.c<b.c;}

bool cmp2(Point a,Point b){return a.id<b.id;}

inline Num min(Num a,Num b){return a<b?a:b;}

inline void add(int s,int t,Num f){

  edge *p=new(edge);p->t=t;p->f=f;p->nxt=g[s];g[s]=p;

  p=new(edge);p->t=s;p->nxt=g[t];

  g[t]=p;g[s]->pair=g[t];g[t]->pair=g[s];

}

Num sap(int v,Num flow){

  if(v==T)return flow;

  Num rec;

  for(edge *p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&zero<p->f){

    Num ret=sap(p->t,min(flow-rec,p->f));

    p->f-=ret;p->pair->f+=ret;d[v]=p;

    rec+=ret;

    if(rec==flow)return flow;

  }

  d[v]=g[v];

  if(!(--gap[h[v]]))h[S]=T;

  gap[++h[v]]++;

  return rec;

}

void work(){

  scanf("%d",&n);

  S=n*2+1;T=S+1;

  for(i=1;i<=T;i++)g[i]=NULL,gap[i]=h[i]=0;

  for(i=1;i<=n;i++)scanf("%d",&val[i].a),val[i].id=i,val[i].del=0;

  for(i=1;i<=n;i++)scanf("%d",&val[i].b);

  for(i=1;i<=n;i++)scanf("%d",&val[i].c);

  maxf=0;

  for(i=1;i<=n;i++){

    f[i]=1;

    for(j=1;j<i;j++)if(val[j].a<val[i].a&&f[i]<f[j]+1)f[i]=f[j]+1;

    for(j=1;j<i;j++)if(val[j].a<val[i].a&&f[i]==f[j]+1)add(j*2,i*2-1,inf);

    if(maxf<f[i])maxf=f[i];

  }

  for(i=1;i<=n;i++){

    if(f[i]==1)add(S,i*2-1,inf);

    if(f[i]==maxf)add(i*2,T,inf);

  }

  std::sort(val+1,val+n+1,cmp1);

  for(i=1;i<=n;i++)add(val[i].id*2-1,val[i].id*2,Num(val[i].b)-Num(0,i-1));

  maxflow=Num();

  for(gap[i=0]=T;i++<T;)d[i]=g[i];

  while(h[S]<T)maxflow+=sap(S,inf);

  tmp=Num(maxflow.x+1)-maxflow;

  for(i=cnt=0;i<n;i++)if(tmp.ex[i/62]&(1LL<<(61-i%62)))val[i+1].del=1,cnt++;

  printf("%d %d\n",maxflow.x+1,cnt);

  std::sort(val+1,val+n+1,cmp2);

  for(i=1,flag=0;i<=n;i++)if(val[i].del)printf(flag?" %d":"%d",i),flag=1;

  puts("");

}

int main(){

  inf.x=~0U>>2;

  for(i=0;i<BIT;i++)inf.ex[i]=MOD;

  zero=Num();

  scanf("%d",&Test);

  while(Test--)work();

  return 0;

}

　　

相关文章