CF102428F Fabricating Sculptures 题解

发表于 2022-11-09 分类于题解本文字数： 652 阅读时长 ≈ 2 分钟

题目大意是，给定两个整数 $n$ 和 $m$ ，我们需要统计出长度为 $n$ 的序列的数量，其中序列满足两个条件：

$\sum_{i = 1}^{n} a_{i} = m$
$\forall i \in (1, n), a_{i} \geq min (a_{i - 1}, a_{i + 1})$

形象一点来说，我们不能出现三个相邻的元素按照 “高 - 低 - 高” 的顺序排列。

我们考虑最终得到的序列的大致形状。
因为我们上面的约束条件，我们每一行必须是连续的，同时长度必须不小于其下面的那一行。

那么我们考虑对行的状态进行 DP，而不是列的状态。
那我们可以设一个 $f_{i, j}$ ，表示当前 DP 了 $i$ 列，总和为 $j$ 的合法方案数。
我们考虑对其进行转移：
我们可以枚举一个 $k$ ，代表当前我们的下一行会在这一行的基础上增加 $k$ ，可以得到如下的式子：

$\begin{matrix} (1) & f_{i, j} = f_{i, j - i} + \sum_{k = 1}^{i - 1} f_{i - k, j - i} \times (k + 1) \end{matrix}$

两种情况分别代表直接把上一行复制过来的情况，此时只有一种可能的排布；还有比上一行多 $k$ 个的情况，此时我们可以枚举多出来的这 $k$ 个分别怎样分布，其中左边填充个数的取值为 $[0, k]$ 范围内的整数，总共有 $k + 1$ 种可能性。

这样转移会超时，考虑使用前缀和来优化。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5010;
const ll mod = 1e9 + 7;
int n, m;
ll sum[N * 2], psum[N];
ll f[N][N];
int main()
{
    scanf("%d%d", &n, &m);
    m -= n;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            psum[j] = (psum[j] + sum[j]) % mod;
            if(j == 0)f[i][j] = 1;
            else f[i][j] = psum[j];
            sum[i + j] = (sum[i + j] + f[i][j]) % mod;
        }
    }
    printf("%lld\n", f[n][m]);
    return 0;
}