HDU 3998 Sequence （SAP+DP）

Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 946    Accepted Submission(s): 325

Problem Description

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).

 

 

Input

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

 

 

Output

The output have two line. The first line is s and second line is num.

 

 

Sample Input

4 3 6 2 5

 

 

Sample Output

2 2

 

 

Source

2011 Multi-University Training Contest 16 - Host by TJU

 

 

Recommend

lcy

 

 

 

 

思路：思路跟最短路径+最大流是一样的，用最大流去限定，求出最短路径的个数。同样，求出最长上升子序列，再用最大流去限定，求出的结果就是最长上升子序列的个数。求LCIS则用常规方法，既定义数组dp[i]是表示以 i 结尾的最长上升子序列的长度，求出最长序列ans。由于数列中的每一个数只能使用一次，构图的时候需要拆点。若有n个数，则拆成2 * n个点，构造源点和汇点，将每个点都和自己拆出来的点连边，将源点和最长序列为1的点连边，将最长序列为ans的点与汇点连边，最后若dp[j] = dp[i] + 1,则将i + n和 j连边。所有边的流量都是1，这样便可以限制每个点只使用一次。其实连边的顺序就是最长序列为1，2，3，...，ans。可以理解为从最长序列为1（该数本身）一直流到数列中的最长上升序列。画出图来就好理解了。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int N=500010;
const int INF=0x3f3f3f3f;

struct Edge{
    int to,nxt;
    int cap;
}edge[N<<1];

int n,cnt,head[N],dp[N],num[N];
int dep[N],gap[N],cur[N],aug[N],pre[N];

void addedge(int cu,int cv,int cw){
    edge[cnt].to=cv;  edge[cnt].cap=cw;  edge[cnt].nxt=head[cu];
    head[cu]=cnt++;
    edge[cnt].to=cu;  edge[cnt].cap=0;   edge[cnt].nxt=head[cv];
    head[cv]=cnt++;
}

int LCIS(){         //求出最长上升子序列 
    for(int i=1;i<=n;i++)
        dp[i]=1;   // dp[i]是表示以 i 结尾的最长上升子序列的长度
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++)
            if(num[i]>num[j] && dp[j]+1>dp[i])
                dp[i]=dp[j]+1;
        ans=max(ans,dp[i]);
    }
    return ans;
}

int src,des;

int SAP(int n){
    int max_flow=0,u=src,v;
    int id,mindep;
    aug[src]=INF;
    pre[src]=-1;
    memset(dep,0,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]=n;
    for(int i=0;i<=n;i++)
        cur[i]=head[i]; // 初始化当前弧为第一条弧
    while(dep[src]<n){
        int flag=0;
        if(u==des){
            max_flow+=aug[des];
            for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
                id=cur[v];
                edge[id].cap-=aug[des];
                edge[id^1].cap+=aug[des];
                aug[v]-=aug[des];   // 修改可增广量，以后会用到
                if(edge[id].cap==0) // 不回退到源点，仅回退到容量为0的弧的弧尾
                    u=v;
            }
        }
        for(int i=cur[u];i!=-1;i=edge[i].nxt){
            v=edge[i].to;    // 从当前弧开始查找允许弧
            if(edge[i].cap>0 && dep[u]==dep[v]+1){  // 找到允许弧
                flag=1;
                pre[v]=u;
                cur[u]=i;
                aug[v]=min(aug[u],edge[i].cap);
                u=v;
                break;
            }
        }
        if(!flag){
            if(--gap[dep[u]]==0)    /* gap优化，层次树出现断层则结束算法 */
                break;
            mindep=n;
            cur[u]=head[u];
            for(int i=head[u];i!=-1;i=edge[i].nxt){
                v=edge[i].to;
                if(edge[i].cap>0 && dep[v]<mindep){
                    mindep=dep[v];
                    cur[u]=i;   // 修改标号的同时修改当前弧
                }
            }
            dep[u]=mindep+1;
            gap[dep[u]]++;
            if(u!=src)  // 回溯继续寻找允许弧
                u=pre[u];
        }
    }
    return max_flow;
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d",&n)){
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        int ans=LCIS();
        src=0;  des=2*n+1;
        for(int i=1;i<=n;i++){  
            addedge(i,n+i,1);   //将每个点都和自己拆出来的点连边, 容量为1
            if(dp[i]==1)    //将源点和最长序列为1的点连边
                addedge(src,i,1);
            if(dp[i]==ans)  //将最长序列为ans的点与汇点连边
                addedge(n+i,des,1);
            for(int j=i+1;j<=n;j++)
                if(dp[j]==dp[i]+1)  //最后若dp[j] = dp[i] + 1,则将i + n和 j连边
                    addedge(n+i,j,1);   //所有边的流量都是1，这样便可以限制每个点只使用一次
        }
        printf("%d\n%d\n",ans,SAP(2*n+2));
    }
    return 0;
}