hdu 3998 Sequence --最长上升子序列+最大流
/*题意：给出一个序列，问该序列的最长上升子序列的长度是多少，以及相同长度的，组成元素完全不同的最长上升子序列的个数。思路：第一问用O(n^2)的dp求解，第二问就是最多不相交路径了。设最长上升子序列的长度为k，第一问解决后，dp数组中保存的是以这个数结尾的最长上升子序列的长度，于是把每个数拆成两个点i和i’，中间连容量为1的边，表示每个数只能选一次，dp值为1的与源点连边，dp值为k的与汇点连边，容量均为无穷，然后枚举所有的i和j（j<i），如满足dp[j]+1==dp[i]且a[j]<a[i]，则从j’向i连一条容量无穷的边，然后求最大流即可。另外此题由于数据规模较小，可以采用求出最长升序列后，枚举删除最长升序列的做法，如此重复多次，也可求得结果，复杂度O(n^3)。*/#include<stdio.h>#include<string.h>#define inf 0x7fffffffint data[100010],dp[100010];int n,m;struct edge//边 { int u,v,f,next,b,c;//边的 前节点 后节点 可用流 下条边的编号 原来边上流的上下界 }e[1000000]; int head[1000000],s,t,yong,ind,sum; int d[1000000],num[1000000]; int min(int a,int b){return a<b?a:b;} int pro(){int ret=0,i,j,k;memset(dp,0,sizeof(dp));dp[0]=1;for(i=1;i<n;i++){k=-1;for(j=0;j<i;j++){if(data[j]<data[i]&&(k==-1||dp[k]<dp[j]))k=j;}if(k!=-1)dp[i]=dp[k]+1;else dp[i]=1;if(dp[i]>ret)ret=dp[i];}return ret;//返回值居然写成了dp[n-1] 很长时间没有写代码 生疏了}void adde(int u,int v,int f){e[yong].f=f,e[yong].u=u,e[yong].v=v;e[yong].next=head[u],head[u]=yong++;e[yong].f=0,e[yong].u=v,e[yong].v=u;e[yong].next=head[v],head[v]=yong++;}void build(){int i,j;yong=0;memset(head,-1,sizeof(head));//2n点 0--2n-1 s=2n,t=2n+1;s=2*n,t=2*n+1;for(i=0;i<n;i++)adde(2*i,2*i^1,1);for(i=0;i<n;i++){if(dp[i]==1)adde(s,2*i,inf);if(dp[i]==m)adde(2*i^1,t,inf);}for(i=0;i<n;i++){if(dp[i]<m){for(j=i+1;j<n;j++){if(data[i]<data[j]&&dp[j]==dp[i]+1)adde(2*i^1,2*j,inf);}}}}int sap_gap(int u,int f,int s,int t){ if(u==t) return f; int i,v,mind=t,last=f,cost; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; int flow=e[i].f; if(flow>0) { if(d[u]==d[v]+1) { cost=sap_gap(v,min(last,flow),s,t); e[i].f-=cost; e[i^1].f+=cost; last-=cost; if(d[s]>=t+1) return f-last; if(last==0) break; } if(d[v]<mind) mind=d[v]; } } if(last==f) { --num[d[u]]; if(num[d[u]]==0) d[s]=t+1; d[u]=mind+1; ++num[d[u]]; } return f-last; } int pro2(){build();int f=0; memset(d,0,sizeof(d)); memset(num,0,sizeof(num)); for(num[s]=t+1;d[s]<t+1;) f+=sap_gap(s,inf,s,t); return f;}int main(){int i;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&data[i]);m=pro();printf("%d\n",m);m=pro2();printf("%d\n",m);}return 0;}