Sequence

4
3 6 2 5

2
2

方一：dp+最大流       （我所用的方法）

方二：思路：可以用n*log(n)的做法求出最长上升子序列，然后删除原数组中的这些数，再求最长上升子序列（如果长度减小，则直接退出）。

题意：给一个序列X（x[1] , x[2] , ....x[n]） ， 个数为n 。求最长递增子序列长度，及 最长递增子序列的个数。要求：1):  x[i1] < x[i2],...,<x[ik];（ 1<=i1 < i2,...,<ik<=n ）  2):每个数只能使用一次。

解题：对于第一问：最长递增子序列的长度ans   很好求。现在对于求第二问，我们先记下求最长递增子序列时每个数属于哪些位置（即长度）。先来做个假设：如果一个数num在记录的第2个位置，且以num为最小值，能找到一个长度为ans的最长递增子序列，那么 我们可以再加一个数（第1个位置的数）到此序列中，此时最长递增子序列长度为 ans+1,  因ans < ans+1，所以与先前求出的最长递增子序列长度ans矛盾。所以假设不成立 。  

结论：一个最长递增子序列的起始数一定是从第1个位置中的数开始。这也就是为什么下面用 最大流 来解的最重要的原因。 

建图：（1）先每个看成一个点，然后把每个点i 拆成两个点建一条边：i -->(i+n) 边容为 1（拆点后，i 点只进不出，i+n点只出不入，除了自身边）。（2）再把源点s=0与第1个位置的每个点 i 建一条边容量为 1 ：s-->i。（3）把每ans位置的每个点与汇点 t = 2*n+1 建一条边容量为1：（i+n）-->t。（4）第len长度的点 u 与第len+1长度的点 v 建一条边容量为1。满足的要求：题意中的 1）和 2）。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define captype int

const int MAXN = 100010;   //点的总数
const int MAXM = 400010;    //边的总数
const int INF = 1<<30;
struct EDG{
    int to,next;
    captype cap,flow;
} edg[MAXM];
int eid,head[MAXN];
int gap[MAXN];  //每种距离(或可认为是高度)点的个数
int dis[MAXN];  //每个点到终点eNode 的最短距离
int cur[MAXN];  //cur[u] 表示从u点出发可流经 cur[u] 号边
int pre[MAXN];

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
//有向边 三个参数，无向边4个参数
void addEdg(int u,int v,captype c,captype rc=0){
    edg[eid].to=v; edg[eid].next=head[u];
    edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;

    edg[eid].to=u; edg[eid].next=head[v];
    edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;
}
captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    pre[sNode] = -1;
    gap[0]=n;
    captype ans=0;  //最大流
    int u=sNode;
    while(dis[sNode]<n){   //判断从sNode点有没有流向下一个相邻的点
        if(u==eNode){   //找到一条可增流的路
            captype Min=INF ;
            int inser;
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to])    //从这条可增流的路找到最多可增的流量Min
            if(Min>edg[i].cap-edg[i].flow){
                Min=edg[i].cap-edg[i].flow;
                inser=i;
            }
            for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){
                edg[i].flow+=Min;
                edg[i^1].flow-=Min;  //可回流的边的流量
            }
            ans+=Min;
            u=edg[inser^1].to;
            continue;
        }
        bool flag = false;  //判断能否从u点出发可往相邻点流
        int v;
        for(int i=cur[u]; i!=-1; i=edg[i].next){
            v=edg[i].to;
            if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){
                flag=true;
                cur[u]=pre[v]=i;
                break;
            }
        }
        if(flag){
            u=v;
            continue;
        }
        //如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1
        int Mind= n;
        for(int i=head[u]; i!=-1; i=edg[i].next)
        if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){
            Mind=dis[edg[i].to];
            cur[u]=i;
        }
        gap[dis[u]]--;
        if(gap[dis[u]]==0) return ans;  //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径
                                        //因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流
        dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1
        gap[dis[u]]++;
        if(u!=sNode) u=edg[pre[u]^1].to;  //退一条边
    }
    return ans;
}

int binarySearch(int* dp , int num ,int ans){
    int l=1 , r = ans , mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(dp[mid]>=num)
            r = mid-1;
        else
            l=mid+1;
    }
    return l;
}
int main(){
    int n , num[MAXN] , dp[MAXN];
    while(scanf("%d",&n)>0){
        for(int i=1; i<= n; i++)
            scanf("%d",&num[i]),dp[i]= INF;

        int ans=0;  //最长递增子序列的长度
        vector<vector<int> >vct;
        vct = vector<vector<int> >(n,vector<int>(0,0));

        for(int i=1; i<= n; i++){
            int len= binarySearch(dp,num[i],ans);
            vct[len].push_back(i);
            if(dp[len]>num[i]) dp[len]=num[i];
            if(ans<len) ans=len;
        }
        init();
        int s = 0, t = 2*n+1;
        for(int i=1; i<=n; i++) //拆点，自身点看作一条边，每个点只能用一次所以容量为1
            addEdg( i , i+n , 1 );
        for(int i=vct[1].size()-1; i>=0; i--)
            addEdg(s , vct[1][i] , 1);
        for(int i=vct[ans].size()-1; i>=0; i--)
            addEdg(vct[ans][i]+n , t , 1);

        for(int len = 1; len<ans; len++)
        for(int i = vct[len].size()-1 ; i>=0; i--){
            int u=vct[len][i];
            for(int j = vct[len+1].size()-1 ; j>=0; j--){
                int v=vct[len+1][j];
                if(u > v)break;                 //如果v位置在u的位置前方，则不能满足:1<=i1 < i2,...,<ik<=n
                if(num[u]>=num[v]) continue;    
                addEdg(u+n , v , 1);
            }
        }

        int k=maxFlow_sap(s , t , t+1); //最长递增子序列的个数，相当寻找（s-->t）路的条数,每个边只能用一次
        printf("%d\n%d\n",ans,k);
    }
}

HDU 3998 Sequence （最长递增子序列+最大流SAP,拆点法）经典

原文：http://blog.csdn.net/u010372095/article/details/46564943