最长递增子序列问题

解题思路

本题有三问，第一问很简单，是一个简单的线性dp，设 $f[i]$ 表示前 $i$ 个数的最长递增子序列，那么 $f[i] = \max_{j < i, ~a[j] \leq a[i]} \lbrace f[j] + 1, 1 \rbrace$。

第二问是每个数只能用一次，问我们能取出来多少个最长递增子序列（长度为 $s$），这里可以用到网络流来解决，对于 $f[i]$ 如果能从 $f[j]$ 转移过来，那么我们就从第 $j$ 个节点向第 $i$ 个节点连一条边，通过这样一个方式我们能得到一个有向图。那么对于图中每一条从 $f[]$ 值为 $1$ 到 $f[]$ 值为 $s$ 的完整的路径（长度是 $s$ 的路径），都是一个合法的最长递增子序列，是一一对应的。

因此第二问对应到这个图中，就是问我们最多有多少条没有公共点的长度是 $s$ 的路径。没有公共点就意味着每个点只能用一次，对点有限制可以使用拆点技巧，将所有点都拆成入点和出点，入点向出点连一条容量为 $1$ 的边，就可以保证每个点只被用一次。另外流网络中还有源点和汇点，由于我们要找的是所有长度为 $s$ 的路径，意味着起点必须是所有 $f[]$ 值是 $1$ 的点，终点必须是所有 $f[]$ 值是 $s$ 的点，因此从源点向所有起点连一条边，从所有终点向汇点连一条边。

通过以上的方式完善整张图，再在图中求最大流，就是第二问的答案。

第三问在第二问上再做升级，让第 $1$ 个点和第 $n$ 个点可以用多次，只需要放开这两个点只能用一次的限制即可，将和这两个点有关的边的容量设置成 $+\infty$ 就行了，也不需要重新建图，根据残量网络的性质，在求完第二问的残量网络的基础上重新做一次增广再将增广出来的流量累加到第二问的答案上，就是第三问的答案。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 251010, INF = 0x3f3f3f3f;

int n, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
int f[N], a[N]; //dp数组、原序列

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，并判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点最多能传输的流量，传输上限是 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //dinic 求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

    S = 0, T = n * 2 + 1; //源点、汇点
    for(int i = 1; i <= n; i++) add(i, i + n, 1); //从所有点的出点向入点连一条容量为 1 的边

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    int s = 0; //最长递增子序列的长度
    for(int i = 1; i <= n; i++) //dp求最长递增子序列（模板）
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(a[j] <= a[i])
                f[i] = max(f[i], f[j] + 1); //状态转移方程

        for(int j = 1; j < i; j++)
            if(a[j] <= a[i] && f[i] == f[j] + 1)
                add(j + n, i, 1); //找出所有能转移到 i 的 j，从 j 向 i 连一条容量为 1 的边

        s = max(s, f[i]); //记录最长递增子序列的长度
    }

    for(int i = 1; i <= n; i++)
        if(f[i] == 1) add(S, i, 1); //从源点向所有 f 值为 1 的点连一条容量为 1 的边
        else if(f[i] == s) add(n + i, T, 1); //从所有 f 值为 s 的点向汇点连一条容量为 1 的边

    printf("%d\n", s);

    //特判，如果最长递增子序列的长度为 1，说明是递减序列，第二问第三问都是 n
    if(s == 1) printf("%d\n%d\n", n, n);
    else //否则需要具体统计
    {
        int res = dinic(); //第二问的答案就是之前建出来的图的最大流
        printf("%d\n", res);

        //第三问需要将和第 1 个点、第 n 个点有关的边的容量改为 INF
        for(int i = 0; i < idx; i += 2)
        {
            int a = e[i ^ 1], b = e[i];
            if(a == S && b == 1) w[i] = INF;
            else if(a == 1 && b == 1 + n) w[i] = INF;
            else if(a == n && b == n + n) w[i] = INF;
            else if(a == n + n && b == T) w[i] = INF;
        }
        printf("%d\n", res + dinic()); //将新增广的流量累加到第二问上，就是第三问的答案
    }
    return 0;
}