[**P2766** 最长不下降子序列问题](https://www.luogu.org/problemnew/show/P2766)

时间：2021-07-13 15:39:50

P2766 最长不下降子序列问题

考虑我们是如何\(dp\)这个\(LIS\)的。

我们是倒着推，设置\(dp(i)\)代表以\(i\)为起点的\(LIS\)是多少。转移太显然了

\[dp(i)=max\{dp(j)\}+1,data[i]\le data[j]
\]

想一想一个合法的\(LIS\)方案代表着什么，代表着它是由这个式子一个一个推出来的。

考虑一个数字只能用一次，那么我们直接拆成两个点\(v_0,v_1\)分别代表一个数字的入度和出度，连一条\(v_1v_2,cap=1\)的边。这样就模拟了一个数字可以被前面多个都相中但是只能往后面相中一个的要求。

考虑如何构造方案，这个东西是个灵感，就是还原\(dp\)的过程，这样就可以得到合法方案。

模型这样建立

\[(i_0,i_1,1)
\\
(S,i_0,inf),dp(i)=1
\\
(i_1,T,inf),dp(k)=ans
\]

这样就好了。

实际上，这样建模体现了"且"的关系，这种建模方式在以后可能大有用处。

#include<bits/stdc++.h>

using namespace std;typedef long long ll;

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define RP(t,a,b)  for(register int t=(a),edd=(b);t<=edd;++t)

#define ERP(t,a)   for(register int t=head[a];t!=-1;t=e[t].nx)

#define midd register int mid=(l+r)>>1

#define TMP template < class ccf >

#define lef l,mid,pos<<1

#define rgt mid+1,r,pos<<1|1

#define pushup(pos) (seg[pos]=seg[pos<<1]+seg[pos<<1|1])

TMP inline ccf qr(ccf b){

    register char c=getchar();register int q=1;register ccf x=0;

    while(c<48||c>57)q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)x=x*10+c-48,c=getchar();

    return q==-1?-x:x;}

TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}

TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}

TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}

TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}

TMP inline void READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}

//----------------------template&IO---------------------------

const int maxn=5e2+15;

const int maxm=maxn<<3;

int dp[maxn];

int data[maxn];

const int inf=0x3f3f3f3f;

int n,S,T;

struct E{

    int to,w,nx;

}e[maxm<<1],tmp[maxm<<1];

int cnt(-1);

int head[maxm];

int id[maxn][2];

int sz;

int ans1,ans2,ans3;

int d[maxm];

int cur[maxm];

inline void add(int fr,int to,int w,bool f){

    e[++cnt]=(E){to,w,head[fr]};head[fr]=cnt;

    if(f) add(to,fr,0,0);

}

queue < int > q;

inline bool bfs(){

    while(not q.empty()) q.pop();

    RP(t,1,sz) cur[t]=head[t],d[t]=inf+1;

    d[S]=1;q.push(S);

    while(not q.empty()){

	register int now=q.front();q.pop();

	if(now==T) break;

	ERP(t,now){

	    if(d[e[t].to]>d[now]+1&&e[t].w>0){

		d[e[t].to]=d[now]+1;

		q.push(e[t].to);

	    }

	}

    }

    return d[T]<inf;

}

int dfs(int now,int fl){

    if(now==T||!fl) return fl;

    register int ret=0;

    for(register int t=cur[now],en;t!=-1;t=e[t].nx){

	cur[now]=t;

	if(d[e[t].to]==d[now]+1){

	    en=dfs(e[t].to,Min(fl,e[t].w));

	    if(en){e[t].w-=en;e[t^1].w+=en;fl-=en;ret+=en;}

	    if(not fl)break;

	}

    }return ret;

}

inline void dinic(int& ret){while(bfs()) ret+=dfs(S,inf);}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

    memset(head,-1,sizeof head);

    n=qr(1);

    READ(data,n);

    RP(t,1,n) dp[t]=1;ans1=1;

    DRP(t,n,1) RP(i,t+1,n) if(data[t]<=data[i]) ans1=Max((dp[t]=Max(dp[t],dp[i]+1)),ans1);

    S=++sz;T=++sz;

    DRP(t,n,1){

	id[t][0]=++sz;id[t][1]=++sz;

	add(id[t][0],id[t][1],1,1);

	if(dp[t]==1){add(id[t][1],T,inf,1);}

	if(dp[t]==ans1){add(S,id[t][0],inf,1);}

	RP(i,t+1,n) if(data[i]>=data[t]&&dp[i]+1==dp[t]) add(id[t][1],id[i][0],1,1);

    }

    RP(t,0,cnt) tmp[t]=e[t];

    dinic(ans2);

    RP(t,0,cnt) e[t]=tmp[t];

    add(id[1][0],id[1][1],inf,1);

    add(id[n][0],id[n][1],inf,1);

    dinic(ans3);

    if(ans1==1) ans2=ans3=n;

    printf("%d\n%d\n%d\n",ans1,ans2,ans3);

    return 0;

}

相关文章