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