参考链接：
http://www.cnblogs.com/gentleh/archive/2013/03/30/2989958.html
题意：求一个序列的最长上升子序列，及其个数（注意：两个最长上升子序列不能共有同一个数，才能算两个）
思路：用dp+最大流来求，首先用两次循环dp求出最长上升子序列的长度ans，然后就是建图了，可以选择源点为0，
由于数列中的每一个数只能使用一次，构图的时候需要拆点。若有n个数，则拆成2 * n个点，构造源点s=0和汇点t=2*n+1，
将每个点(i)都和自己拆出来的点(i+n)连边，将源点和dp[i]=1的点连边，将dp[i]=ans的点与汇点连边，
最后若dp[j] = dp[i] + 1,则将i + n和 j连边。所有边的流量都是1，这样便可以限制每个点只使用一次。
其实连边的顺序就是最长序列为1，2，3，...，ans。可以理解为从最长序列为1（该数本身）一直流到数列中的最长上升序列。
这里要注意的是，由于数据弱，有不用拆点也能A的。但是为了保证每个点都是用一次，一定要拆点。
如果不拆点的话，可以见下图，则中间那个点可能会被用两次，具体不仔细说了。
我一开始按照dinic模板打了一遍，结果TLE。。。后来经别人指点，加了dinic中的两个判断条件，见(1)和(2)，瞬间A了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include <queue> #define INF 0x3f3f3f3f using namespace std; const int maxn=1005; int n,m; int a[maxn]; //序列 int pri[maxn*2]; int head[maxn*2]; //因为要拆点 int s,t; //s:源点 t:汇点 int dp[maxn]; int tot=0; int ans,num;//最长上升子序列的长度，以及不同的个数。 struct Edge{ int from,to; int next; int c,f; }edge[maxn*100]; void add(int x,int y,int val){ edge[tot].next=head[x]; edge[tot].from=x; edge[tot].to=y; edge[tot].c=val; //注意这里是c为val，反向边c为0 //edge[tot].f=0; head[x]=tot++; edge[tot].next=head[y]; edge[tot].from=y; edge[tot].to=x; edge[tot].c=0; //edge[tot].f=0; head[y]=tot++; } bool BFS(){ queue<int>q; memset(pri,-1,sizeof(pri)); pri[0]=0;//源点 q.push(0); while(!q.empty()){ int tmp=q.front(); q.pop(); for(int k=head[tmp];k!=-1;k=edge[k].next){ int v=edge[k].to; if(pri[v]==-1 && edge[k].c>0){ pri[v]=pri[tmp]+1; if(v==t){ return true; } q.push(v); } } } return false; } int dinic(int p,int flow){ if(p==t){ return flow; } int f=flow; for(int k=head[p];k!=-1;k=edge[k].next){ int v=edge[k].to; if(pri[v]==pri[p]+1 && edge[k].c>0){ int a=edge[k].c; //a为该边可以增加的流量 int ff=dinic(v,min(a,flow)); //ff为路径中所有a的最小值，即为该条路中可以增加的流量 //edge[k].f+=ff; //edge[k^1].f-=ff; //因为双向边是同时建的，编号必定一奇一偶成对的，如0、1；2、3；4、5； //这样用k异或1即可求得对应的反向边 edge[k].c-=ff; edge[k^1].c+=ff; flow-=ff; if(flow<=0) break; //(1) } } if(f-flow<=0) pri[p]=-1; //(2) //如果从p点流出去的流量<=0，那么设置pri[p]的值为-1，之后在dinic中就不考虑到p点的情况了。 return f-flow; } int main() { while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++){ dp[i]=1; scanf("%d",&a[i]); } for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ if(a[i]>a[j] && dp[j]+1>dp[i]) dp[i]=dp[j]+1; } } m=2*n+1; ans=0; for(int i=1;i<=n;i++){ ans=max(dp[i],ans); } memset(head,-1,sizeof(head)); tot=0; s=0; t=2*n+1; for(int i=1;i<=n;i++){ add(i,i+n,1); if(dp[i]==1) add(s,i,1); if(dp[i]==ans) add(i+n,t,1); } for(int i=1;i<=n;i++){ //下面j只要从i+1开始即可，因为add加边是加双向边的 for(int j=i+1;j<=n;j++){ if(dp[j]==dp[i]+1){ add(i+n,j,1); } } } num=0; while(BFS()){ num+=dinic(s,INF); } printf("%d %d ",ans,num); } return 0; }