首页 > ACM题库 > HDU-杭电 > HDU 3998-Sequence-网络流-[解题报告]HOJ
2015
04-14

HDU 3998-Sequence-网络流-[解题报告]HOJ

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

/*
类似于网络流24题中的一道(求最长上升子序列的最多个数):
构图方案:
首先求出LIS;
然后拆点 建边Edge(i,i+n,1) 因为没个点只能用一次,所以边的容量为1
然后对于每个dp[i]==1的建边Edge(s,i,1)
dp[i]==k的建边Edge(i+n,t,1);
dp[i]==dp[j]+1 建边Edge(j+n,i,1);
然后sap 求最大流就OK了
*/
#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;
int head[M],p[M],k,n;
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));
    FF(i,NV) cur[i] = head[i];
    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].next = head[u];
    head[u] = NE++;
    E[NE].c = 0;
    E[NE].pos = u;
    E[NE].next = head[v];
    head[v] = NE++;
}
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(head,-1,sizeof(head));
       // memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }
        k=LIS();
        for(i=1;i<=n;i++)
        {
            addEdge(i,i+n,1);
            if(dp[i]==1)
            addEdge(source,i,1);
            if(dp[i]==k)
            addEdge(i+n,sink,1);
            for(j=i+1;j<=n;++j)
               if(dp[j]==dp[i]+1)addEdge(i+n,j,n);
        }
        printf("%d\n%d\n",k,sap(source,sink));
    }
    return 0;
}
/*
4
3 6 2 5
*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/azheng51714/article/details/8060480


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * 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;
    }