Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 54 Accepted Submission(s): 18
as x[i1], x[i2],...,x[ik], which satisfies follow conditions:
1) x[i1] < x[i2],...,<x[ik];
2) 1<=i1 < i2,...,<ik<=n
As an excellent program designer, you must know how to find the maximum length of the
increasing sequense, which is defined as s. Now, the next question is how many increasing
subsequence with s-length can you find out from the sequence X.
For example, in one case, if s = 3, and you can find out 2 such subsequence A and B from X.
1) A = a1, a2, a3. B = b1, b2, b3.
2) Each ai or bj(i,j = 1,2,3) can only be chose once at most.
Now, the question is:
1) Find the maximum length of increasing subsequence of X(i.e. s).
2) Find the number of increasing subsequence with s-length under conditions described (i.e. num).
have n numbers.
4 3 6 2 5
2 2
#include<cstdio>
using namespace std;
const int mm=2222222;
const int mn=11111;
const int oo=1000000000;
int node,src,dest,edge;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn],a[mn],f[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c)
{
ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=next[i])
if(flow[i]&&dis[v=ver[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=next[i])
if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int main()
{
int i,j,n,ans;
while(scanf("%d",&n)!=-1)
{
for(i=1;i<=n;++i)scanf("%d",&a[i]),f[i]=1;
for(i=2;i<=n;++i)
for(j=1;j<i;++j)
if(a[j]<a[i]&&f[j]>=f[i])f[i]=f[j]+1;
for(i=ans=1;i<=n;++i)
if(f[i]>ans)ans=f[i];
prepare(n+n+2,0,n+n+1);
for(i=1;i<=n;++i)
{
addedge(i,i+n,1);
if(f[i]==1)addedge(src,i,1);
if(f[i]==ans)addedge(i+n,dest,1);
for(j=i+1;j<=n;++j)
if(f[j]==f[i]+1)addedge(i+n,j,1);
}
printf("%d\n",ans);
printf("%d\n",Dinic_flow());
}
return 0;
}