Libre 6005 「网络流 24 题」最长递增子序列 / Luogu 2766 最长递增子序列问题（网络流，最大流）

Description

问题描述：

给定正整数序列x1,...,xn 。

（1）计算其最长递增子序列的长度s。

（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。

（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。

编程任务：

设计有效算法完成（1）（2）（3）提出的计算任务。

Input

第1 行有1个正整数n，表示给定序列的长度。接下来的1 行有n个正整数n:x1, ..., xn。

Output

第1 行是最长递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。

Sample Input

4

3 6 2 5

Sample Output

2

2

3

Http

Libre:

Luogu:

Source

网络流，最大流

解决思路

看清题目，不是最长递增子序列是最长不下降子序列。

这道题目首先运用动态规划的方式求出最长不下降子序列，这也是第一问的内容。注意，本题不能使用单调队列的方式，因为要求出到每一个数的最长不下降子序列长度（后面记为F），这在后两问中要用。

那么如何求解第二问呢？

我们把每一个数拆成两个点入点和出点，在每一个数的入点和出点之间连容量为1的边，同时设置一个源点一个汇点。从前往后扫描每一个数，若发现第i个数的F[i]==最长不下降子序列长度，则在源点与i的出点之间连一条容量为1的边。若F[i]==1，则在其出点与汇点之间连一条容量为1的边。并且，对于任何数i，扫描其前面的每一个数j，若F[i]==F[j]+1且第j位的数<=第i位的数，则在i的出点与j的入点之间连一条容量为1的边。

这样建图，有点类似于分层图的思想，从最高层的F为最长不下降子序列长度，往下每一层长度减一，直到最底下一层长度为1。这样我们跑一边最短路就可以了。

至于第三问，我们只要在重新建图的时候把1到汇点,1的入点到出点，n的入点到出点，源点到n（如果存在的话）这几条边设置为无穷大即可。

但要注意，第三问要特判一下递减的情况，因为这样最长不下降子序列长度为1，跑最大流会出现无穷大的流的情况。

另：这里用Dinic求解最大流，具体请移步我的

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxN=2000;const int maxM=maxN*maxN*4;const int inf=147483647;class Edge{public:    int u,v,flow;};int n;int cnt=-1;int F[maxN];int Arr[maxN];int Head[maxN];int Next[maxM];Edge E[maxM];int depth[maxN];int cur[maxN];int Q[maxM];void Add_Edge(int u,int v,int flow);bool bfs();int dfs(int u,int flow);int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)        scanf("%d",&Arr[i]);    for (int i=1;i<=n;i++)//动态规划求出最长不下降子序列    {        F[i]=1;        for (int j=1;j
         
          0)) { depth[v]=depth[u]+1; h++; Q[h]=v; } } } while (t!=h); if (depth[n*2+1]==-1) return 0; return 1;}int dfs(int u,int flow){ if (u==n*2+1) return flow; for (int &i=cur[u];i!=-1;i=Next[i]) { int v=E[i].v; if ((depth[v]==depth[u]+1)&&(E[i].flow>0)) { int di=dfs(v,min(flow,E[i].flow)); if (di>0) { E[i].flow-=di; E[i^1].flow+=di; return di; } } } return 0;}