最长不下降子序列

给你n个数,第一问要求求出最长不下降子序列长度s,第二问在每个数字只使用一次的情况下,求出长度为s的不下降子序列有多少个,第三问\(a_1\)和\(a_n\)可以使用无限次的情况下长度为s的不下降子序列有多少个。
解 第一问用n^2的lis求解,并存dp[i]为从1到i的最长不下降子序列长度,然后因为每个点只能使用一次,所以使用拆点,对于dp[i]为1的地方,建源点往i.x边权为1,对于dp[i]为s的地方建i.y往汇点边权为1,然后对于每个i,建i.x往i.y边权为1(保证每个点只会使用一次),然后对于满足\(i>j\)并且\(a_i>=a_j\)并且\(dp[a_i]==dp[a_j]+1\)的点,从j.y往i.x连边权为1。跑最大流即为第二问
再是第三问 将汇点到1.x的边权改成inf,1.x往1.y的边权改成inf,n.x往n.y的边权改成inf,n.y往汇点的边权改成inf(前提是有这个边),再跑一边最大流(残余增广路),加上第二问的答案即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 2000;
const ll maxm = 100000;
struct Edge{
	ll from, to, cap, flow;
	Edge(){
	}
	Edge(ll from, ll to, ll cap, ll flow):from(from), to(to), cap(cap), flow(flow){}	
};
struct Edge1
{
    ll from, to; ll dist;       //起点,终点,距离
    Edge1(ll from, ll to, ll dist):from(from), to(to), dist(dist) {}
};
struct Dinic{
	ll n, m, s, t;
	vector<Edge>edges;
	vector<ll>G[MAXN];
	ll d[MAXN];
	ll cur[MAXN];
	ll vis[MAXN];
	void init(ll n, ll s, ll t)
	{
		this->n = n;this->s = s;this->t = t;
		edges.clear();
		for(ll i = 0;i <= n;++i) G[i].clear();
	}
	
	void add_edge(ll from, ll to, ll cap)
	{
		edges.push_back( Edge(from, to, cap, 0) );
		edges.push_back( Edge(to, from, 0, 0) );
		m = edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1); 
	}
	
	bool bfs(){
		memset(vis, 0, sizeof(vis));
		queue<ll>Q;
		Q.push(s);
		d[s] = 0;
		vis[s] = true;
		while(!Q.empty())
		{
			ll x = Q.front();
			Q.pop();
			for(ll i = 0;i < G[x].size();++i)
			{
				Edge& e = edges[G[x][i]];
				if(!vis[e.to] && e.cap > e.flow)
				{
					vis[e.to] = true;
					d[e.to] = d[x] + 1;
					Q.push(e.to);
				}
			}		
		}
		return vis[t];
	}
	ll dfs(ll x,ll a)
	{
		if(x == t || a == 0)return a;
		ll flow = 0, f;
		for(ll& i = cur[x];i < G[x].size();++i)
		{
			Edge& e = edges[G[x][i]];
			if(d[x] + 1 == d[e.to] && (f = dfs( e.to, min(a, e.cap-e.flow)))>0)
			{
				e.flow += f;
				edges[G[x][i]^1].flow -= f;
				flow += f;
				a -= f;
				if(a == 0)break; 
			}
		}
		return flow;
	}
	ll maxflow()
	{
		ll flow = 0;
		while(bfs())
		{
			memset(cur, 0, sizeof(cur));
			flow += dfs(s,inf);
		}
		return flow;
	}
}gao;//刘汝佳网络流dinic板子
int a[505];
int dp[505];
int main()
{
	int n;
	scanf("%d",&n);
	gao.init(2*n+2,2*n+1,2*n+2);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		dp[i]=1;
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>=a[j]){
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++){
		if(dp[i]==1){
			gao.add_edge(n*2+1,i,1);
		}
		if(dp[i]==ans){
			gao.add_edge(i+n,n*2+2,1);
		}
		gao.add_edge(i,i+n,1);
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>=a[j]&&dp[i]==dp[j]+1){
				gao.add_edge(j+n,i,1);
			}
		}
	}
	ll tmp=gao.maxflow();
	printf("%lld\n",tmp);
	if(n==1){
		printf("%lld\n",tmp);
		return 0;
	}
	gao.add_edge(2*n+1,1,inf);
	gao.add_edge(1,n+1,inf);
	if(dp[n]==ans){
		gao.add_edge(n,2*n+2,inf);
		gao.add_edge(n,2*n,inf);
	}
	printf("%lld\n",tmp+gao.maxflow());
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注