2015
04-14

# Sequence

There is a sequence X (i.e. x[1], x[2], …, x[n]). We define increasing subsequence of X
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).

The input file have many cases. Each case will give a integer number n.The next line will
have n numbers.

The input file have many cases. Each case will give a integer number n.The next line will
have n numbers.

4
3 6 2 5

2
2

/*

dp[i]==k的建边Edge(i+n,t,1);
dp[i]==dp[j]+1 建边Edge(j+n,i,1);

*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define M 10100
int gap[M],dis[M],pre[M],cur[M],dp[M];
int NE,NV,sink,source;
struct Node
{
int c,pos,next;
} E[999999];
#define FF(i,NV) for(int i=0;i<NV;i++)
int sap(int s,int t)
{
//memset(pre,-1,sizeof(pre));
memset(dis,0,sizeof(int)*(NV+1));
memset(gap,0,sizeof(int)*(NV+1));
int u = pre[s] = s,maxflow = 0,aug = 1<<29;
gap[0] = NV;
while(dis[s] < NV)
{
loop:
for(int &i = cur[u]; i != -1; i = E[i].next)
{
int v = E[i].pos;
if(E[i].c && dis[u] == dis[v] + 1)
{
aug=min(aug,E[i].c);
pre[v] = u;
u = v;
if(v == t)
{
maxflow += aug;
for(u = pre[u]; v != s; v = u,u = pre[u])
{
E[cur[u]].c -= aug;
E[cur[u]^1].c += aug;
}
aug = 1<<29;
}

goto loop;
}
}

int mindis = NV;
for(int i = head[u]; i != -1 ; i = E[i].next)
{
int v = E[i].pos;
if(E[i].c && mindis > dis[v])
{
cur[u] = i;
mindis = dis[v];
}
}
if( (--gap[dis[u]]) == 0)break;
gap[ dis[u] = mindis+1 ] ++;
u = pre[u];
}
return maxflow;
}
void addEdge(int u,int v,int c )
{
E[NE].c = c;
E[NE].pos = v;
E[NE].c = 0;
E[NE].pos = u;
}
int LIS()
{
int i,j,ans=0;
dp[1]=1;
for(i=2;i<=n;++i)
{
dp[i]=1;
for(j=1;j<i;++j)
{
if(p[j]<p[i]&&dp[j]>=dp[i])dp[i]=dp[j]+1;
}
ans=max(ans,dp[i]);
}
return ans;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
NE=source=0;
sink=n<<1|1;
NV=sink+1;
// memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
k=LIS();
for(i=1;i<=n;i++)
{
if(dp[i]==1)
if(dp[i]==k)
for(j=i+1;j<=n;++j)
}
printf("%d\n%d\n",k,sap(source,sink));
}
return 0;
}
/*
4
3 6 2 5
*/


1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}