【题解】【数位DP】P4798 卡尔文球锦标赛

本文最后更新于：2024年1月16日 晚上 18:54

[CEOI2015 Day1] 卡尔文球锦标赛

题目描述

译自 CEOI2015 Day1 T2「Calvinball championship」

一场卡尔文球比赛会有 \(n\) 名选手参与，他们的编号分别为 \(1\dots n\)，分为若干个非空的球队。我们规定球队之间按照每个球队编号最小的选手的编号排序，并且以从 1 开始的连续整数编号。

举个栗子，譬如 1 号选手自己成一队，2, 3 和 5 号选手成一队，4 和 6 号选手成一队。

> \(\ \texttt{1}\)
> \(\ \texttt{2 3 5}\)
> \(\ \texttt{4 6}\)

那么 1 号选手的球队就是 1 号球队，2 号选手的球队就是 2 号球队，4 号选手的球队就是 3 号球队。

> \(\ \texttt{1|1}\)
> \(\ \texttt{2|2 3 5}\)
> \(\ \texttt{3|4 6}\)

每个人每天会选择不同的球队，我们可以在记录时省略选手的编号，仅记录每个位置对应选手所属球队编号的序列（上述例子为 1 2 2 3 2 3），因为每天的选手是一样的。当可能的选择方案全部被使用过后，锦标赛就结束了。

由于选择方案十分多，选择困难症患者纷纷表示力不从心。今年，我们决定根据记录的序列的字典序来选择方案。因此，第一天，所有人都在一个队 1 1 1 1 1；第二天，所有人都与 6 号针锋相对 1 1 1 1 1 2……在最后一天，所有人互相打响战争 1 2 3 4 5 6。

对于给定的球队记录，请你算出将会在未来的哪一天使用该记录。输出这个数字对 \(1\ 000\ 007\) 取余的结果。

输入格式

第一行，一个正整数 \(n(1 \leq n \leq 10\ 000)\)。

第二行，\(n\) 个以空格分隔的正整数，表示任务所给的球队记录。

输出格式

输出一个正整数，表示任务所给的球队记录将会被使用的天数对 \(1\ 000\ 007\) 取余的结果。第一天的天数为 1。

样例 #1

样例输入 #1

1
2
3
1 2 2

样例输出 #1

1
4

提示

请注意，三人比赛中可能的选择有 1 1 1 1 1 2 1 2 1 1 2 2 和 1 2 3。

数据范围与提示

数据点 \(1-3\) \(4-5\) \(6-7\) \(8-10\)
\(n\le\) \(14\) \(100\) \(1\ 000\) \(10\ 000\)

时间限制 1.00s

内存限制 62.50MB

题解

把每个人的球队编号看作是一个数位，搜索满足要求的所有数。因此，我们可以用数位 DP 来解决这个问题。

66分题解：记忆化搜索的数位DP

用递归很快就能写出来，但是肯定会爆MLE。

思路和数位DP模板的一样，也有 \(limit\) 来指示当前位是否有上限。

\(dp[pos][preMax]\) 表示当前位为 \(pos\)，前pos位（包括当前的第pos位）的最大值为 \(preMax\) 的方案数。这个是没有 \(limit\) 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N = 10007;
#define MOD 1000007
int n, a[N], dp[N][N];  // dp[pos][preMax] 表示当前位为 pos，前 pos 位（包括当前的第 pos 位）的最大值为 preMax 的方案数
int dfs(int pos, int preMax, bool limit) {
    if (pos == n) return 1;
    if (!limit && dp[pos][preMax]) return dp[pos][preMax];  // 由于 dp[pos][preMax] 的值至少为 1，所以不用初始化为 -1，直接判断是否为 0 即可
    int ans = 0;
    int up = limit ? a[pos + 1] : preMax + 1;
    for (int i = 1; i <= up; i++)
        ans = (ans + dfs(pos + 1, max(preMax, i), limit && i == up)) % MOD;
    if (!limit) dp[pos][preMax] = ans;
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << dfs(1, 0, true);
    return 0;
}

100分题解：使用迭代的数位DP + 自滚动数组优化空间

我们可以先写一个迭代的版本，然后再进行优化。

通过对 \(dp[pos][preMax]\) 的分析，我们可以发现它有 \(preMax+1\) 个子节点。

所有子情况，如图所示：

  • \(dp[pos+1][preMax]\) 图中节点的所有的左子节点（包括中间的子节点）

  • \(dp[pos+1][preMax+1]\) 图中节点的最右边的子节点

转移方程为：

\[dp[pos][preMax] = dp[pos+1][preMax] \times preMax + dp[pos+1][preMax+1]\]

n=4的DP解空间树

我们再来看看数值受到上界限制的情况，

每个 \(limited\) 为真的节点，其子节点可以分为两类：

  • \(dp[pos+1][preMax+1]\)

  • \(limited[pos+1]\)

如图所示，对于受限制的节点，其方案数递推方程为：

\[limited[pos]=dp[pos+1][preMax]\times (A[pos+1]-1) + limited[pos+1]\]

limited[pos] 的子节点情况，编号序列为 A=\{1,2,3,4,1,1,2\}

根据 \(limited[pos]\) 和 \(dp[pos][preMax]\) 的递推方程，我们可以写出迭代的版本：

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
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 10007;
#define MOD 1000007
int n, a[N], maxn[N], dp[N][N], limited[N];
int iterate() {
    if (n == 1) return 1;
    limited[n] = 1;
    for (int i = 1; i <= n; i++) dp[n][i] = 1;
    for (int pos = n - 1; pos >= 1; pos--) {
        // 计算limited部分
        limited[pos] = (1ll * dp[pos + 1][maxn[pos]] * (a[pos + 1] - 1)) % MOD + limited[pos + 1];
        limited[pos] %= MOD;
        // 计算dp部分
        for (int preMax = 1; preMax <= pos; preMax++) {
            dp[pos][preMax] = (1ll * dp[pos+1][preMax] * preMax + dp[pos+1][preMax+1]) % MOD;
        }
    }
    return limited[1];
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxn[i] = max(maxn[i - 1], a[i]);
    }
    cout << iterate();
    return 0;
}

这样做空间复杂度为 \(O(n^2)\)，显然超出了内存限制。所以用滚动数组优化一下。

这也是为什么我们要先写迭代版本，因为dfs必须要用到 \(dp[pos][preMax]\) 的所有值，所以无法优化空间。（或许用bfs可以优化？）

下是最终的滚动数组优化版本，非常简洁。

时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(n)\)。

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
26
#include <bits/stdc++.h>
using namespace std;
const int N = 10007, MOD = 1000007;
int n, a[N], maxn[N], dp[N];
int iterate() {
    int limited = 1;
    if (n == 1) return limited;
    for (int i = 1; i <= n; i++) dp[i] = 1;
    for (int pos = n - 1; pos >= 1; pos--) {
        limited = ((1ll * dp[maxn[pos]] * (a[pos + 1] - 1)) % MOD + limited) % MOD;
        for (int i = 1; i <= pos; i++) dp[i] = (1ll * dp[i] * i + dp[i + 1]) % MOD;
    }
    return limited;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxn[i] = max(maxn[i - 1], a[i]);
    }
    cout << iterate();
    return 0;
}

效率非常好，时间 384ms，内存 680KB。全场最快好吧。 :D

轻松干到最优解第一
题解
#DP #数位DP
【题解】【数位DP】P4798 卡尔文球锦标赛
https://qalxry.github.io/2024/01/16/【题解】【数位DP】P4798-CEOI2015-Day1-卡尔文球锦标赛/
作者
しずり雪
发布于
2024年1月16日
更新于
2024年1月16日
许可协议