给定正整数序列 x1…,xn
1.计算其最长不下降子序列的长度 ss。
2.如果每个元素只允许使用一次,计算从给定的序列中最多可取出多少个长度为 ss 的不下降子序列。
3.如果允许在取出的序列中多次使用 x1 xn(其他元素仍然只允许使用一次),
则从给定序列中最多可取出多少个不同的长度为 ss 的不下降子序列
建模:
求出Fi ,
Fi ==1 Add(S,i,1)
Fi==len Add(i+n,T,1)
这题每个点只能选一次,相当于点权,所以点i拆开, Add(i ,i+n,1)
对于F[j]+1=F[i] , Add(j,i+n,1)
#include <iostream> #include<cmath> #include <queue> #include <cstring> using namespace std; const int N =2e6+2,M=5e4+100; int g[N],a[N],L; const int inf =1e9+7; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T,n,m; int dis[M],ans=0,now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<M;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } signed main(){ int i,j,k; cin>>n; for(i=1;i<=n;i++) cin>>a[i],g[i]=1; for(i=1;i<=n;i++) for(k=1;k<i;k++) if(a[i]>=a[k]) g[i]=max(g[i],1+g[k]); for(i=1;i<=n;i++) L=max(L,g[i]); if(L==1){ printf("1\n%d\n%d\n",n,n); return 0 ; } cout<<L<<endl; S=0,T=2*n+1; for(i=1;i<=n;++i) if(g[i]==1) add_(S,i,1) ; for(i=1;i<=n;i++) if(g[i]==L) add_(i+n,T,1); for(i=1;i<=n;++i) add_(i,i+n,1); for(i=1;i<=n;i++) for(k=1;k<i;k++) if(g[i]==g[k]+1&&a[i]>=a[k]) add_(k+n,i,1); int ans=0; while(bfs()) ans+=dfs(S,inf) ; cout<<ans<<endl; add_(1,1+n,inf); add_(S,1,inf); if(g[n]==L) add_(n,2*n,inf),add_(2*n,T,inf); while(bfs()) ans+=dfs(S,inf) ; cout<<ans<<endl; }
标签:int,go,序列,now,P2766,最长,hd,dis From: https://www.cnblogs.com/towboa/p/17241341.html