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;
    }