DP问题全记录

Q1 CF2135A

我们定义一个块(block)为其中所有元素都等于数组长度的数组。例如，$[3,3,3]$、$[1]$ 和 $[4,4,4,4]$ 都是块，而 $[1,1,1]$ 和 $[2,3,3]$ 则不是。

若一个数组可以通过任意数量(可能为零)的块连接而成，则称其为整洁数组(neat array)。注意空数组总是整洁的。

给定一个由 n 个整数组成的数组 a，请找出其最长的整洁子序列∗的长度。

∗序列 c 是序列 a 的子序列，当且仅当 c 可以通过从 a 的任意位置删除若干个(可能为零或全部)元素得到。

Ac代码

void solve()
{
    int n;
    cin >> n;
    vint a(n + 1);
    for (size_t i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // dp[i] 表示idx = i 时候前面可构造序列的最长长度
    // 初始化？ 显然都为 0
    // 转移方程？
    // 可以选择是否加入dp[i]
    // 如果不加入dp[i] , 则有 dp[i] = dp[i - 1]
    // 如果选择加入 dp[i]
    // 这意味着我们必须从当前位置向前找到计数数目减去a[i]的元素然后用其坐标x下的dp[x] + a[i] 来更新dp[i]
    // 什么时候可以将a[i]加入dp？即当计数数目等于a[i]时候
    vint dp(n + 1, 0);
    map<int, deque<int>> re;
    // re[a[i]] 为 元素 a[i] 下标构成的集合
    for (size_t i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        re[a[i]].emplace_back(i);
        if (re[a[i]].size() > a[i]) {
            re[a[i]].pop_front();
        }
        if (re[a[i]].size() == a[i]) {
            dp[i] = max(dp[i], dp[re[a[i]].front() - 1] + a[i]);
        }
    }
    cout << dp[n] << endl;
}

Problem - 2134D

Background

若存在一种将每个下标 $i$ 染成红色或蓝色的方式，使得对于所有满足 $b_i>b_j$ 的下标对 $i<j$，$i$ 和 $j$ 被分配的颜色均不同，则称序列 $b_1,b_2,\dots ,b_k$ 是好的

给定序列 $a_1,a_2,\dots ,a_n$。计算该序列中所有好的子序列的数量(包括空子序列${}^{\text{∗}}$)。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

${}^{\text{∗}}$若序列 $b$ 可通过从序列 $a$ 中任意位置删除零个或多个元素得到，则称 $b$ 是 $a$ 的子序列。

显然，对于题目所描述的”良好”实际上是要求我们寻找最长递减子序列(LDS)不超过 2 的所有子序列

那我们的需求就是统计所有LDS不超过2的子序列，对于统计子序列的问题，我们可以使用动态规划(dp)的思路来解决

具体来说，就是对于当前元素，我们可以选择两种方式加入dp中，具体而言，就是：“选择当前元素i”,“不选当前元素”

那么接下来我们还有一个问题，就是如何在线性时间下统计当前元素的LDS？

我们可以为每一个元素统计一个前缀最大值和左侧存在最大值的一个前缀值最大mp，当有元素低于前缀值的时候，我们就可以认为这个这个序列LDS > 2

对于mp，你可以认为将前缀所有LDS = 2的那个元素拉出来取最大

对于状态转移方程，我们可以这样定义dp

dp[i][m][mp]为前i个元素中选择的子序列的个数，最大的元素m以及我们规定的元素mp

• 如果不选择元素i
  • 从dp[i][m][mp] = dp[i-1][m][mp]
• 如果选择元素i
  • dp[i][ai][mp] = dp[i - 1][m][mp] ($a_i>m$)
  • dp[i][m][ai] = dp[i - 1][m][mp] $(mp\le a_i<m)$

AC solution

void solve()
{
    i64 n;
    cin >> n;
    vint a(n + 1, 0), b(n + 1, 0);
    for (i64 i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (i64 i = 1; i <= n; i++) {
        b[i] = 1;
        for (i64 j = i + 1; j <= n; j++) {
            if (a[i] > a[j]) b[i]++;
        }
        for (i64 j = 1; j < i; j++) {
            if (a[i] >= a[j]) b[i]++;
        }
    }
    // 每一个单独的子序列都是一个结果，其为1
    // dp[i][m][mp]表示前i个元素中选择的子序列的数目，最大的元素m以及我们规定的LDS = 2的最大值mp
    vector<vector<vector<i64>>> dp(2, vvint(n + 1, vint(n + 1, 0)));
    dp[0][0][0] = 1;
    i64 cr = 0;
    for (i64 i = 1; i <= n; i++) {
        i64 x = b[i];
        cr ^= 1;
        for (i64 j = 0; j <= n; j++) {
            for (i64 k = 0; k <= n; k++) {
                dp[cr][j][k] = dp[cr ^ 1][j][k];
            }
        }
        for (i64 j = 0; j <= n; j++) {
            for (i64 k = 0; k <= j; k++) {
                // 如果前一个为0
                if (dp[cr ^ 1][j][k] == 0) continue;
                // a[i] > max
                if (j > x && x > k) dp[cr][j][x] = (dp[cr][j][x] + dp[cr ^ 1][j][k]) % MOD;
                // a[i] < max ，a[i] > mp
                if (x > j) dp[cr][x][k] = (dp[cr][x][k] + dp[cr ^ 1][j][k]) % MOD;
            }
        }
    }
    i64 ans = 0;
    for (i64 i = 0; i <= n; i++) {
        for (i64 j = 0; j <= n; j++) {
            ans = (ans + dp[cr][i][j]) % MOD;
        }
    }
    cout << ans % MOD << endl;
}