ABC262G 题解

LIS with Stack

观察到 \(n \le 50\)，考虑区间 dp。设 \(dp(l, r, x, y)\) 表示区间 \([l, r]\) 中选出的子序列的最小值 \(\ge x\)，最大值 \(\le y\) 的方案数。

根据栈的性质，设元素 \(x\) 入栈的时间为 \(in_x\)，出栈时间为 \(out_x\)，那么所有元素构成的区间 \([in_x, out_x]\) 两两之间要么包含要么不交。根据此性质可以设计出 dp 状态的转移。

对于状态 \(dp(l, r, x, y)\)，枚举 \(a_l\) 是什么时候出栈的，假设把它弹出去的元素是 \(a_k\) 满足 \(x \le a_k \le y \land a_l < a_k\)，那么有：

可以删掉 \(a_l\)，有 \(dp(l, r, x, y) = \max\{dp(l, r, x, y), dp(l + 1, r, x, y)\}\)。

也可以刚把 \(a_l\) 入栈就直接出栈，即 \(dp(l, r, x, y) = \max\{dp(l, r, x, y), dp(l + 1, r, x, a_l) + 1\}\)。

总时间复杂度 \(O(n^5)\)，因为区间 dp 有各种 \(\dfrac{1}{2}\) 常数所以跑得很快。

代码：

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        std::cin >> A[i];
    }

    constexpr int V = 50;
    std::vector dp(N + 1, std::vector(N + 1, std::vector(V + 1, std::vector<int>(V + 1, 0))));

    auto Pre_Work = [&](auto &dp) {
        for (int len = 2; len <= V; ++len) {
            for (int x = 1, y = len; y <= V; ++x, ++y) {
                dp[x][y] = std::max({dp[x][y], dp[x + 1][y], dp[x][y - 1]});
            }
        }
    } ;

    for (int i = 1; i <= N; ++i) {
        dp[i][i][A[i]][A[i]] = 1;
        Pre_Work(dp[i][i]);
    }

    for (int len = 2; len <= N; ++len) {
        for (int l = 1, r = len; r <= N; ++l, ++r) {
            for (int x = 1; x <= V; ++x) {
                for (int y = x; y <= V; ++y) {
                    dp[l][r][x][y] = dp[l + 1][r][x][y];
                    if (A[l] < x || A[l] > y) {
                        continue;
                    }
                    dp[l][r][x][y] = std::max(dp[l][r][x][y], dp[l + 1][r][x][A[l]] + 1);
                    for (int k = l + 1; k <= r; ++k) {
                        if (std::max(x, A[l] + 1) <= A[k] && A[k] <= y) {
                            int res = dp[l + 1][k - 1][x][A[l]] + 1;
                            res += dp[k][r][A[l]][y];
                            dp[l][r][x][y] = std::max(dp[l][r][x][y], res);
                        }
                    }
                }
            }
            Pre_Work(dp[l][r]);
        }
    }

    std::cout << dp[1][N][1][V] << "\n";

    return 0;
}