洛谷P2766 最长不下降子序列问题题解

题意：

给定正整数序列 \(x_1 \ldots, x_n\)。

计算其最长不下降子序列的长度 \(s\)。

如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 \(s\) 的不下降子序列。

如果允许在取出的序列中多次使用 \(x_1\) 和 \(x_n\)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 \(s\) 的不下降子序列。

令 \(a_1, a_2, \ldots, a_s\) 为构造 \(S\) 时所使用的下标，\(b_1, b_2, \ldots, b_s\) 为构造 \(T\) 时所使用的下标。且 \(\forall i \in [1,s-1]\)，都有 \(a_i \lt a_{i+1}\)，\(b_i \lt b_{i+1}\)。则 \(S\) 和 \(T\) 不同，当且仅当 \(\exists i \in [1,s]\)，使得 \(a_i \neq b_i\)。

输入格式：

第一行有一个正整数 \(n\)，表示给定序列的长度。接下来的一行有 \(n\) 个正整数\(x_1, ..., x_n\)。

输出格式：

第 \(1\) 行是最长不下降子序列的长度 \(s\)。

第 \(2\) 行是可取出的长度为 \(s\) 的不下降子序列个数。

第 \(3\) 行是允许在取出的序列中多次使用 \(x_1\) 和 \(x_n\) 时可取出的长度为 \(s\) 的不同的不下降子序列个数。

数据范围：

\(1 \le n\le 500\)

第一问就是萌萌dp，~~我觉得 cxy 都能做~~。

考虑第二问怎么做。

每个点只能用一次，考虑拆点，把 \(i\) 拆成 \(i_{x},i_{y}\) ，\(i_x\) 向 \(i_y\) 连一条流量为 \(1\) 的边。

因为要是最长不下降子序列，所以选点 \(j\) 的下一个点 \(i\) 时，要严格满足 \(f_j = f_i - 1\) 。

因此我们将这样的 \(j_y\) 向 \(i_x\) 连边，流量为 \(1\) （因为对于这样的 \((j,i)\) 只支持一次匹配）

然后 \(s\) 向 \(f_i=1\) 的 \(i_x\) 连边，流量为 \(1\) 。\(f_i=s\) 的 \(i_y\) 向 \(t\) 连边，流量为 \(1\) 。

跑一遍最大流就是答案。

第三问其实就是稍微改了一改：

\(j=1\) 时，\((j,i)\) 可以匹配多次，对应边 \((1,i)\) 。
\(j=n \land f_n = s\) 时，\(n \to t\) 可以有多条匹配，对应边 \((n,t)\) 。
还有 \(j_x \to j_y~(j=1\lor(j=n\land f_n=s))\) 也可以匹配多条。

我们直接在残量网络上建新边，流量为 \(+\infty\) ，再跑一遍最大流即可，注意这是在第二问基础上的增量。

注意这里有一个很特殊的情况，需要特判，即输入 1 1 的时候，第三问我们会建出来这样的图

这个时候跑出来的最大流会变成 \(+\infty\) ，所以需要特判一下，答案是 \(1\) 。

理论时间复杂度 \(\mathcal{o}(n^4)\) ，因为边数其实远小于 \(\mathcal{O}(n^2)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(505 * 2 + 15))
#define M ((int)(N * N * 2 + 3 * N * 2))

int n,m,s,t,tot,pos=1,a[N],dp[N],dep[N],now[N],head[N];
// A : 1 ~ n, A' : n+1 ~ n+n
struct Edge { int u,v,w,next; } e[M];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void add(int u,int v,int w) { addEdge(u,v,w); addEdge(v,u,0); }
queue<int> q;
bool bfs()
{
    for(int i=1; i<=tot; i++) dep[i] = INF;
    dep[s] = 1; q.push(s); now[s] = head[s];
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            if(e[i].w > 0 && dep[v] == INF)
            {
                dep[v] = dep[u] + 1;
                now[v] = head[v]; q.push(v);
            }
        }
    }
    return dep[t] != INF;
}
int dfs(int u,int in)
{
    if(u == t) return in;
    int out = 0;
    for(int i=now[u]; i && in; i = e[i].next)
    {
        int v = e[i].v; now[u] = i;
        if(e[i].w > 0 && dep[v] == dep[u] + 1)
        {
            int res = dfs(v, min(in, e[i].w));
            e[i].w -= res; e[i ^ 1].w += res;
            in -= res; out += res;
        }
    }
    if(!out) dep[u] = INF;
    return out;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; s = n + n + 1; tot = t = s + 1;
    if(n == 1) { return cout << "1\n1\n1\n", 0; }
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=n && (dp[i] = 1); i++)
    {
        for(int j=1; j<i; j++)
            if(a[j] <= a[i]) up(dp[i], dp[j] + 1);
        up(m, dp[i]);
    }
    cout << m << '\n';
    for(int i=1; i<=n; i++) add(i, n + i, 1); // A -> A'
    for(int i=1; i<=n; i++) if(dp[i] == 1) add(s, i, 1); // s -> A
    for(int i=1; i<=n; i++) if(dp[i] == m) add(n + i, t, 1); // A' -> t
    for(int i=1; i<=n; i++) for(int j=1; j<i; j++)
        if(a[j] <= a[i] && dp[i] - 1 == dp[j]) add(n + j, i, 1); // x -> y
    int res = 0;
    while(bfs()) res += dfs(s,INF);
    cout << res << '\n';
    add(1, n + 1, INF); add(s, 1, INF);
    if(dp[n] == m) { add(n + n, t, INF); add(n, n + n, INF); }
    while(bfs()) res += dfs(s,INF);
    cout << res << '\n';
    return 0;
}