题意：给定一个序列，，求最长上升子序长度以及有多少组，每个元素只能用一次。
思路：先求LIS,记为num，求出以每个点为末尾的最长子序列长度。窝们将每个点点拆成i和i’,i –> i’ 容量为1,源点连接d[ i ]=1的点，容
量为1，汇点连接d[ i ]=num的点，容量为1。对于j<i, a[ j ] < a[ i ]，d[ i ] = d[ j ] + 1的情况，j’ –> i 连一条容量为1的边，跑最大流即可。详见代码：
/********************************************************* file name: hdu3998.cpp author : kereo create time: 2015年02月17日 星期二 16时43分44秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=2000+50;const int MAXN=100000+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=1000000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int n,edge_cnt,top;int a[N],g[N],d[N];int head[N],que[N],s[N],cur[N],gap[N],dep[N];vector<int>mp[N];struct Edge{int v,cap,flow,next;}edge[MAXN<<1];void init(){edge_cnt=top=0;memset(head,-1,sizeof(head));for(int i=1;i<=n;i++)mp[i].clear();}void addedge(int u,int v,int cap){edge[edge_cnt].v=v; edge[edge_cnt].cap=cap;edge[edge_cnt].flow=0; edge[edge_cnt].next=head[u]; head[u]=edge_cnt++;edge[edge_cnt].v=u; edge[edge_cnt].cap=0;edge[edge_cnt].flow=0; edge[edge_cnt].next=head[v]; head[v]=edge_cnt++;}void bfs(int st,int ed){int front=0,rear=0;memset(gap,0,sizeof(gap));memset(dep,-1,sizeof(dep));dep[ed]=0; gap[0]=1; que[rear++]=ed;while(front!=rear){int u=que[front++];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(dep[v]!=-1)continue;dep[v]=dep[u]+1; gap[dep[v]]++; que[rear++]=v;}}}int isap(int st,int ed){bfs(st,ed);memcpy(cur,head,sizeof(head));int ans=0,u=st;while(dep[st]<2*n+2){if(u == ed){int Min=inf,inser;for(int i=0;i<top;i++){if(edge[s[i]].cap-edge[s[i]].flow<Min){Min=edge[s[i]].cap-edge[s[i]].flow;inser=i;}}for(int i=0;i<top;i++)edge[s[i]].flow+=Min,edge[s[i]^1].flow-=Min;ans+=Min; top=inser;u=edge[s[top]^1].v;continue;}int flag=0,v;for(int i=cur[u];i!=-1;i=edge[i].next){v=edge[i].v;if(edge[i].cap>edge[i].flow && dep[v]+1 == dep[u]){flag=1; cur[u]=i;break;}}if(flag){s[top++]=cur[u]; u=v;continue;}int d=2*n+2;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(edge[i].cap>edge[i].flow && dep[v]<d){cur[u]=i,d=dep[v];}}gap[dep[u]]–;if(!gap[dep[u]])return ans;dep[u]=d+1; gap[dep[u]]++;if(u!=st)u=edge[s[–top]^1].v;}return ans;}int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)g[i]=inf;int num=0;for(int i=1;i<=n;i++){int k=lower_bound(g+1,g+n+1,a[i])-g;d[i]=k; g[k]=a[i];num=max(num,d[i]);}printf("%d\n",num);init();for(int i=1;i<=n;i++){if(d[i] == 1)addedge(0,i,1);else{int k=d[i]-1;for(int j=0;j<mp[k].size();j++)if(a[mp[k][j]-n]<a[i])addedge(mp[k][j],i,1);}mp[d[i]].push_back(i+n);}for(int i=1;i<=n;i++)addedge(i,i+n,1);for(int i=0;i<mp[num].size();i++)addedge(mp[num][i],2*n+1,1);printf("%d\n",isap(0,2*n+1));}return 0;}
耿耿于怀着过去和忐忑不安着未来的人，也常常挥霍无度着现在。
