CF102428F Fabricating Sculptures 题解

发表于 分类于 本文字数： 652 阅读时长 ≈ 2 分钟

true
Fabricating Sculptures
2019-2020 ACM-ICPC Latin American Regional Programming Contest
none
none
  • CF Gym 102428 F

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

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

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

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

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

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

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

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}