题目传送门：HDOJ 7304 [2023杭电多校] Out Of Control

题意

给长度为 $n$ 的序列 $a_n$ 以及 $k$ ，问容量分别为 $i \in k$ 时，有多少种取 $a_j$ 的可能性，取得的序列 $a_1、 a_2、 a_3 ... a_k$ 有如下要求：

$a_i \leq a_j$ ( $1 \leq i < j \leq k$ )
如果先取的 $a_i$ 大于于后取的 $a_j$ ，序列会自动操作：$a_j \leftarrow a_i$

打印可能性的数量，结果 $mod $ $10^9 + 7$ ，其中 $1 \leq n \leq 3000，1 \leq a_i \leq 10^9$

分析

应该是一眼dp，但是怎么找状态及其转移呢，首先我们考虑 $dp_{i,j}$ 是在 $i$ 个长度上，已经取到 $j$ 个数的最大方案数，但是这种会导致 $a$ 会有重复的问题，转移方程不好写；

那么考虑另外一种状态，规定 $dp_{i,j}$ 是在以 $i$ 为长度的不降序序列中，$j$ 为最大元素值的最大方案数

题解

规定 $dp_{i,j}$ 是在以 $i$ 为长度的不降序序列中，$j$ 为最大元素值的最大方案数，转移方程如下

\[dp_{i,j} = \sum_{n = 1}^j dp_{i-1, n} \]

注意一开始要使用去重离散化将 $a_i$ 映射到3000的范围之内，转移时使用前缀和优化可以达到 $O(n^2)$ 复杂度

AC代码

#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int N = 3005, P = 1000000007;
int Case, n, m, i, j, sum, ans, a[N], b[N], f[N][N];
inline void up(int &a, int b) { a = a + b < P ? a + b : a + b - P; }
int main()
{
    scanf("%d", &Case);
    while (Case--)
    {
        scanf("%d", &n);
        for (i = 1; i <= n; i++)
            scanf("%d", &a[i]), b[i] = a[i];
        sort(b + 1, b + n + 1);
        for (m = 0, i = 1; i <= n; i++)
            if (i == 1 || b[i] > b[i - 1])
                b[++m] = b[i];
        for (i = 1; i <= n; i++)
            a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b; // 去重离散化
        sort(a + 1, a + n + 1);
        for (i = 1; i <= m; i++)
            f[1][i] = 1;
        printf("%d\n", m);
        for (i = 2; i <= n; i++)
        {
            sum = ans = 0;
            // for (j = a[i - 1]; j < a[i]; j++)
            if(a[i - 1] < a[i]) up(sum, f[i-1][a[i - 1]]);
            for (j = a[i]; j <= m; j++)
            {
                up(sum, f[i-1][j]); // 求前缀和的过程
                f[i][j] = sum;
                up(ans, sum);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}