?问题描述：
给定正整数序列x1,..., xn。
（1）计算其最长递增子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长
度为s的递增子序列。
注意：这里的最长递增子序列即最长不下降子序列！！！
?编程任务：
设计有效算法完成（1）（2）（3）提出的计算任务。
?数据输入：
由文件alis.in提供输入数据。文件第1 行有1个正整数n(n<=500)，表示给定序列的长度。接
下来的1 行有n个正整数x1,..., xn。
?结果输出:
程序运行结束时，将任务（1）（2）（3）的解答输出到文件alis.out中。第1 行是最长
递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出
的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。
输入文件示例 输出文件示例
alis.in
4
3 6 2 5
alis.out
22
3
第一问，dp。
第二问，拆点，将两个拆出来的点连容量为1的边。
对于每一个f[i]==l的点与s连边，对于每一个f[i]==1的点与t连边，容量都为1.
对于每一对i,j若果i<=j且f[i]==f[j]+1,a[i]<=a[j+1]，也连边。
注意特判整个序列是单调下降序列的情况。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=505;
const int inf=1e9+7;
int n,l,s,t,cnt=1,ans,a[N],f[N],d[2*N],hd[2*N];
queue<int>q;
struct edge
{int to,nxt,f;
}v[2*N*N+4*N];
void addedge(int x,int y,int z)
{v[++cnt].to=y;v[cnt].f=z;v[cnt].nxt=hd[x];hd[x]=cnt;
}
void addedges(int x,int y,int z)
{addedge(x,y,z),addedge(y,x,0);
}
bool bfs()
{memset(d,0,sizeof(d));d[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=hd[u];i;i=v[i].nxt)if(v[i].f&&!d[v[i].to]){d[v[i].to]=d[u]+1;q.push(v[i].to);}}return d[t];
}
int dfs(int u,int lft)
{if(u==t||lft==0)return lft;int r=lft;for(int i=hd[u];i;i=v[i].nxt)if(v[i].f&&r&&d[v[i].to]==d[u]+1){int w=dfs(v[i].to,min(r,v[i].f));v[i].f-=w,v[i^1].f+=w,r-=w;if(!r)return lft;}if(r==lft)d[u]=0;return lft-r;
}
int main()
{freopen("alis.in","r",stdin);freopen("alis.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);f[n]=1;for(int i=n-1;i>=1;i--){for(int j=n;j>i;j--)if(a[i]<=a[j])f[i]=max(f[i],f[j]);f[i]++;l=max(l,f[i]);}printf("%d\n",l);if(l==1){printf("%d\n%d\n",n,n);return 0;}s=0,t=2*n+1;for(int i=1;i<=n;i++){addedges(i,i+n,1);if(f[i]==l)addedges(s,i,1);if(f[i]==1)addedges(i+n,t,1);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]<=a[j]&&f[i]==f[j]+1)addedges(i+n,j,1);while(bfs())ans+=dfs(s,inf);printf("%d\n",ans);cnt=1,ans=0;memset(hd,0,sizeof(hd));for(int i=1;i<=n;i++){int x=1;if(i==1||i==n)x=inf;addedges(i,i+n,x);if(f[i]==l)addedges(s,i,x);if(f[i]==1)addedges(i+n,t,x);}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]<=a[j]&&f[i]==f[j]+1)addedges(i+n,j,1);while(bfs())ans+=dfs(s,inf);printf("%d\n",ans);return 0;
}