LG2766 最长不下降子序列问题最大流网络流24题

问题描述

LG2766

题解

\(\mathrm{Subtask 1}\)

一个求最长不下降子序列的问题，发现\(n \le 500\)，直接\(O(n^2)\)暴力DP即可。

\(\mathrm{Subtask 2}\)

设\(opt_i\)代表区间\([1,i]\)，且以\(i\)为结尾的最长不下降子序列。

考虑拆点，把\(i\)拆成\(i\)和\(i+n\)。

如果\(opt_i=1\)，则从源点向\(i\)连边。

如果\(opt_i=n\)，则从\(i+n\)向汇点连边。

以上两种边边权均为\(INF\)。

接下来从\(i\)向\(i+n\)连边，边权为\(1\)，代表每个数只能使用一次。

接下来枚举\(i,j\)，且\(i<j\)，\(\forall a_j \le a_i\)且\(opt_j=opt_i+1\)，在\(j+n,i\)之间连边，边权为\(1\)。

跑\(\mathrm{Dinic}\)即可。

\(\mathrm{Subtask 3}\)

只需要解除\(1\)和\(n\)的流量限制即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

const int maxn=507;

int n,a[maxn],len=1;

int opt[maxn],ans;

int S,T;

int Head[20000],v[200000],w[200000],tot=1;

int d[20000],Next[200000];

bool bfs(){

	memset(d,0,sizeof(d));

	queue<int>q;q.push(S);d[S]=1;

	while(!q.empty()){

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

		for(int i=Head[x];i;i=Next[i]){

			if(d[v[i]]||!w[i]) continue;

			q.push(v[i]);d[v[i]]=d[x]+1;

			if(v[i]==T) return true;

		}

	}

	return false;

}

int dfs(int x,int flow){

	if(x==T) return flow;

	int rest=flow;

	for(int i=Head[x];i&&rest;i=Next[i]){

		if(d[v[i]]!=d[x]+1||!w[i]) continue;

		int k=dfs(v[i],min(rest,w[i]));

		if(!k) d[v[i]]=0;

		else{

			w[i]-=k,w[i xor 1]+=k;

			rest-=k;

		}

	}

	return flow-rest;

}

void add(int x,int y,int z){v[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;}

int main(){

	read(n);

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

		read(a[i]);opt[i]=1;

	}

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

		for(int j=1;j<i;j++){

			if(a[i]>=a[j]){

				opt[i]=max(opt[i],opt[j]+1);

				len=max(opt[i],len);

			}

		}

	}

	printf("%d\n",len);S=n*2+1,T=S+1;

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

		if(opt[i]==1) add(S,i,1),add(i,S,0);

	}

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

		if(opt[i]==len) add(i+n,T,1),add(T,i+n,0);

	}

	for(int i=1;i<=n;i++) add(i,i+n,1),add(i+n,i,0);

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

		for(int j=1;j<i;j++){

			if(a[i]>=a[j]&&opt[i]==opt[j]+1){

				add(j+n,i,1);add(i,j+n,0);

			}

		}

	}

	while(bfs()){

		int t;

		while(t=dfs(S,0x3f3f3f3f)) ans+=t;

	}

	printf("%d\n",ans);

	add(1,1+n,0x3f3f3f3f);add(n+1,1,0);

	add(S,1,0x3f3f3f3f);add(1,S,0);

	if(opt[n]==len) add(n,n+n,0x3f3f3f3f),add(2*n,n,0),add(n*2,T,0x3f3f3f3f),add(T,n*2,0);

	while(bfs()){

		ans+=dfs(S,0x3f3f3f3f);

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

LG2766 最长不下降子序列问题最大流网络流24题

问题描述

题解

\(\mathrm{Subtask 1}\)

\(\mathrm{Subtask 2}\)

\(\mathrm{Subtask 3}\)

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG2766 最长不下降子序列问题 最大流 网络流24题

问题描述

题解

\(\mathrm{Subtask 1}\)

\(\mathrm{Subtask 2}\)

\(\mathrm{Subtask 3}\)

\(\mathrm{Code}\)

最新文章

热门文章

LG2766 最长不下降子序列问题最大流网络流24题