[CTSC2017]最长上升自序列(伪题解)(Dilworth's theorem+网络流)

部分分做法很多，但每想出来一个也就多5～10分。正解还不会，下面是各种部分分做法：

Subtask 1：k=1

LCS长度最长为1，也就是说不存在j>i和a[j]>a[i]同时成立。显然就是一个LDS，树状数组直接求即可。

Subtask 2：k=2

最多两个，也就是可以由两个LCS拼起来，f[i][j]表示第一个LCS以i结尾，第二个以j结尾的方案数，转移显然。

Subtask 3：k=2

树状数组优化DP，复杂度由$O(n^3)$降为$O(n^2 \log n)$

Subtask 4,5：B<=8

DP套DP：https://www.cnblogs.com/clnchanpin/p/7357564.html

一般与“子序列”同时出现，如最长上升自序列，最长公共自序列等。

Subtask 6,7：

一个显然的定理：一个序列的LCS最大为k意味着这个序列最少可以由k个不相交的LDS组成。

考虑网络流，下面(a,b)表示容量为a，费用为b的边。

拆点，in[x]向out[x]连(1,-1)的边，每次和下一个小于这个数的位置连(1,0)的边，增设源汇，最多增广k次即可。

$O(Kn^3)$

Subtask 8,9：

上面的方法点数为$n$，边数为$n^2$，启发我们用线段树优化建图。

这里用树状数组就行了。

点数$n\log n$，边数$n\log n$。

$O(K(n\log n)^2)$

Subtask 10,11,12：

Johnson多源最短路算法：

传统的Floyd是$O(n^3)$的，已经很优秀了。但是如果我们对每个点跑一次Dijkstra，可以得到$O(n^2\log m)$这个更好的复杂度。

但是Dijkstra不能跑有负权边的情况。

考虑增设超级源S并向每个点连长度为0的边，然后跑单源最短路，接着将每条边(u,v,w)改成(u,v,w+(dis[u]-dis[v]))，其中dis[u]表示S到u的最短路。

这样跑Dijkstra就是正确的了，转移的时候记录pre方便最后求出最短路长度。

不了解如何运用到这道题上。

优化：可以直接用数组代替堆降低复杂度。

Subtask 13～20：

完全不理解的杨氏矩阵理论。

不断分析将复杂度依次降为:$O(n^2\log n+Q\log n)$，$O(n\sqrt{n}\log n)$，$O(n\sqrt{n\log n})$。

附：树状数组+网络流代码(15pts)

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define rep(i,l,r) for (int i=(l); i<=(r); i++)

using namespace std;

const int N=;

int x,y,fir[N],pre[N],a[N],b[N],inq[N],dis[N],n,m,cnt=;

int in[N],out[N],ans[N],BIT[N],S,T,cost,lim,obt,tot;

struct edge{

    int to,nxt,f,c;

    edge () {}

    edge (int x,int y,int z,int l){ to=y; nxt=fir[x]; f=z; c=l; fir[x]=cnt; }

}e[*N];

void add(int x,int y,int z,int l){ e[++cnt]=edge(x,y,z,l); e[++cnt]=edge(y,x,,-l); }

bool spfa(){

    int i,x; queue<int> q;

    for(i=;i<=T;i++) dis[i]=;

    dis[S]=; q.push(S);

    while(!q.empty()){

        x=q.front(); q.pop();

        for(i=fir[x];i;i=e[i].nxt)

            if(e[i].f&&dis[e[i].to]>dis[x]+e[i].c){

                dis[e[i].to]=dis[x]+e[i].c; pre[e[i].to]=i;

                if(!inq[e[i].to]) q.push(e[i].to),inq[e[i].to]=;

            }

        inq[x]=;

    }

    return dis[T]!=;

}

int aug(){

    int x,flow=1e9;

    for(x=T;x!=S;x=e[pre[x]^].to) flow=min(flow,e[pre[x]].f);

    for(x=T;x!=S;x=e[pre[x]^].to)

        cost+=e[pre[x]].c*flow,e[pre[x]].f-=flow,e[pre[x]^].f+=flow;

    return flow;

}

int dinic(){ int res=; while(spfa()) res+=aug(); return res; }

void modify(int p,int x){

    for(;x<=obt;x+=x&-x){

        tot++;

        if(BIT[x]) add(tot,BIT[x],n,);

        add(tot,p,,); BIT[x]=tot;

    }

}

void ask(int p,int x){ for (;x;x-=x&-x) if (BIT[x]) add(p,BIT[x],,); }

int main(){

    freopen("lis.in","r",stdin);

    freopen("lis.out","w",stdout);

    scanf("%d%d",&n,&m);

    if (n>) { rep(i,,m) printf("0\n"); return ; }

    rep(i,,n) scanf("%d",&a[i]),b[i]=a[i];

    sort(b+,b+n+); obt=unique(b+,b+n+)-b-;

    rep(i,,n) a[i]=lower_bound(b+,b+obt+,a[i])-b;

    rep(i,,n) in[i]=i,out[i]=i+n,add(in[i],out[i],,-);

    tot=*n;

    for (int i=n;i;i--) ask(out[i],a[i]),modify(in[i],a[i]);

    S=tot+; T=S+;

    rep(i,,n) add(S,in[i],,),add(out[i],T,,);

    cost=lim=;

    while(spfa()) aug(),ans[++lim]=-cost;

    while(m--) scanf("%d%d",&x,&y),printf("%d\n",ans[min(y,lim)]);

    return ;

}

巴特西

[CTSC2017]最长上升自序列(伪题解)(Dilworth's theorem+网络流)

最新文章

热门文章