NC 213820 [网络流24题]最长递增子序列问题

题目:

• 给定正整数序列x1 ,...... , xn。 （1）计算其最长递增子序列的长度s。 （2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s
的递增子序列。
• 编程任务：设计有效算法完成（1）（2）（3）提出的计算任务。
• 1≤n≤500

题解：

参考自众多大佬题解
第一问好说，经典dp问题，
F[i]，表示以第i位为结尾的最长上升序列的长度
第二三问是网络流问题
因为题目要求是不下降序列，所以我们可以将不下降序列中的数字连边

建图方式：

1. 我们先将每个数字x拆成两个x1，x2，两者连有一个容量为1的有向边，从x1到x2
2. 建立源点S和汇点T，如果序列第x位有F[x]==K,也就是第x位为最长序列的最后一位，那么就建立x2到T连接一条容量为1的有向边
3. 如果F[i] = 1,从S到i1连接一个容量为1的有向边
4. 如果i<j且A[i] < A[j]且F[i]+1=F[j]，从<i.b>到<j.a>连接一条容量为1的有向边。也就是对于一个非递减序列<a,b>,我们连接a2到b1一条有向边，容量为1
   对于第二问，我们直接求网络最大流即可
   对于第三位，我们将边<11,12>,,<n1,n2>,<S,1`>,<n2,T>
   四个边的容量改成无限大，再跑网络最大流即可
   对于一组数 1 6 3 2 5
   对其建边情况如下：
   

   代码：

   #include<bits/stdc++.h>
   #define mem(a) memset(a,0,sizeof(a))
   #define inf 1000000007
   typedef long long ll;
   using namespace std;
   inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
   }
   const int maxn=2e6+9;
   int n;
   int a[maxn];
   int dp[maxn];
   struct node{
    int next;
    int v,w,u;
   }edge[maxn];
   int head[maxn],cnt;
   void add(int u,int v,int w)
   {
    edge[++cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
   }
   int level[maxn];
   bool bfs(int s,int t)
   {
    mem(level);
    queue<int>q;
    q.push(s);
    level[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==t)return 1;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(level[v]==0&&w>0)
            {
                q.push(v);
                level[v]=level[u]+1;
            }
        }
    }
    return 0;
   }
   int dfs(int u,int flow,int t)
   {
    if(u==t)return flow;
    int sum=0;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(level[v]!=level[u]+1||w<=0)continue;
        int tmp=dfs(v,min(flow-sum,w),t);
        edge[i].w-=tmp;
        edge[i^1].w+=tmp;
        sum+=tmp;
        if(sum==flow)return sum;
    }
    if(sum==0)level[u]=inf;
    return sum;
   }
   int main()
   {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i]=1;
    }
    if(n==1)
    {
        cout<<1<<endl<<1<<endl<<1<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<=a[i])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int len=0;
    for(int i=1;i<=n;i++)len=max(len,dp[i]);
    cout<<len<<endl;
    int s=0,t=5000;
    for(int i=1;i<=n;i++)
    {
        if(dp[i]==1)
        {
            add(s,i,1);
            add(i,s,0);
        }
        if(dp[i]==len)
        {
            add(i+n,t,1);
            add(t,i+n,0);
        }
        add(i,i+n,1);
        add(i+n,i,0); 
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[j]<=a[i]&&dp[j]+1==dp[i])
            {
                add(j+n,i,1);
                add(i,j+n,0);
            }
        }
    }
    int ans;
    ans=0;
    while(bfs(s,t))
    {
        ans+=dfs(s,inf,t);
    }
    cout<<ans<<endl;
    add(1,1+n,inf);
    add(1+n,1,0);
    add(s,1,inf);
    add(1,s,0);
    if(dp[n]==len)
    {
        add(n,n*2,inf);
        add(n*2,n,0);
        add(n*2,t,inf);
        add(t,n*2,0);
    }
    while(bfs(s,t))
    {
        ans+=dfs(s,inf,t);
    }
    cout<<ans;
    return 0;
   }