BZOJ3532 : [Sdoi2014]Lis

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;
}

  

上一篇:Spring Data JPA例子[基于Spring Boot、Mysql]


下一篇:jprofiler安装与使用