松松的题目集

发表于 更新于 分类于 ， 本文字数： 3.8k 阅读时长 ≈ 7 分钟

松松的题目集中有 $n$ 道题目 $a_1, a_2, \dots, a_n$，每道题目都只考查一个知识点。松松要按顺序做完其中的所有题目，他有两种做题方法：

  • 无论当前题目考查什么知识点，都可以在 $c_0$ 时间内做完该道题目。
  • 使用含有 $k$ 种知识点的小抄，可以在总共 $c_k$ 的时间内完成所有接下来可做的题目。即当遇到小抄中不包含的知识点题目或已经做完所有题目时，认为当前方法停止，此次做题方法用时 $c_k$ 。每次使用小抄都可以使用与之前不同的小抄，每份小抄最多有 $m$ 个知识点，即 $1 \le k \le m$ 。

聪明的您需要编写一个算法，使得松松能在最短时间内按顺序完成所有的练习题。同时，您还需要计算出在最短时间内做完练习题的方案数。如果做完题目的使用上面两种方法的次数不同，或存在某一个整数 $i$ 满足两种做题方案中的第 $i$ 次做题使用了不同的做题方法或不同的小抄，则称两种做题方案是不同的。如果两份小抄的大小不同，或含有不同的知识点，则称两份小抄是不同的。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据的组数，对于每组测试数据：

第一行输入一个整数 $n (1 \le n \le 6 \times 10^5)$ 表示题目数。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示每个题目考察的知识点。

第三行输入一个整数 $m (1\le m \le 30)$ 表示小抄的知识点上限。

第四行输入 $(m+1)$ 个整数 $c_0,c_1, \dots, c_m (1 \le c_0 \lt c_1 \lt \dots \lt c_m \le 10^9)$ ，其中 $c_0$ 表示使用做题方法一使用的时间 ，$c_i$ 表示使用大小为 $i$ 的小抄需要的时间。

保证所有数据 $n$ 之各不超过 $6 \times 10^5$。

输出格式

每组数据输出一行由单个空格分隔的两个整数，分别是完成所有题目需要的最短时间以及方案数。由于方案数可能很大，请将方案数对 $998244353$ 取模后输出。

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
3
5
1 2 1 3 1
3
4 5 6 100
5
1 2 1 3 1
3
1 2 3 100
7
1 2 3 4 1 1 1
3
4 5 6 7

输出样例

1
2
3
12 1
5 3
13 2

样例解释

对于第一组样例数据，可以首先使用小抄 $\{1,2\}$ 做完前三道题目，然后使用小抄 $\{1,3\}$ 做完最后两道题目。

对于第二组样例数据，以下方案均可以在最短时间内完成所有题目：

  • 使用 $5$ 次方法一
  • 使用小抄 $\{1,2\}$ 做完前三道题目，再使用 $2$ 次方法一
  • 先使用 $2$ 次方法一，再使用小抄 $\{1,3\}$ 除做完 $3$ 个题目

对于第三组样例数据，以下方案均可以在最短时间内完成所有题目：

  • 使用小抄 $\{1,2,3 \}$ 做完前 $3$ 道题目，再用小抄 $\{1, 4\}$ 完成最后两首题目
  • 使用小抄 $\{1,2\}$ 做完前 $2$ 题题目，再使用小抄 $\{1,3,4\}$ 做完最后 $5$ 道题目。

解题

Hint

  • $1 \le c_0 \lt c_1 \lt \dots \lt c_m \le 10^9$
    当我们使用小抄时，小抄中的知识点越多，则使用小抄花费的时间就严格越多。

思路

题目做多后，我们可以较为容易的发现如下两个 $dp$ 。

我们使用 $cost [i]$ 表示完成第 $i$ 个任务花费的最少时间，使用 $f (i, j) = l$ 表示 $a [l \dots i]$ 中有 $j$ 个不同知识点的题目，（ $l$ 为满足条件的最小值）。
$$
cost[i] = min
\begin{cases}
cost[i-1]+c_0,\\
cost[f(i, j)]+c[j], & 1 \le j \le m \ and \ f(i,j)>=1
\end{cases}
$$
方案数也易知，我们使用 $cnt [i]$ 表示完成第 $i$ 个题目花费最少时的方案数，当我们由 $cost [k]$ 推导 $cost [f (i,j)]$ 时，则
$$
cnt[i] =
\begin{cases}
cnt[f(i,j)], & if \ cost[i] > cost[f(i,j)]+c[j] \\
cnt[i]+cnt[f(i,j)], & if \ cost[i] ==cost[f(i,j)]+c[j]
\end{cases}
$$
这段 dp 用代码写来就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i=1; i<=n; i++)
{
    // 方法一
    cost[i] = cost[i-1]+c[0];
    cnt[i] = cnt[i-1];

    for(int j=1; j<=min(m, i); j++)
    {
        int l = f[i][j];

        if(cost[i] > cost[l]+c[j])
        {
            cost[i] = cost[l]+c[j];
            cnt[i] = cnt[l];
        }
        else if(cost[i] == cost[l]+c[j])
        {
        	cnt[i] = (cnt[i]+cnt[l])%MOD;
        }

        if(l == 0)
        	break;
    }
}

我们还要解决另一个问题，就是如何快速地求取 $f (i,j)$ 。如果我们暴力的话，每次都暴力地向前寻找， 由于 $n \le 6 \times 10^5$，这里在用例设计上会被出题者卡。这里引出这题的第三个 dp。

我们用 $f [i][j] = x$ 表示区间 $[x+1, j]$ 有 $j$ 个不同的知识点，$x$ 为满足该条件的最小值 。转移方程为
$$
f[i, j] =
\begin{cases}
f [i-1][j-1], & 如果知识点 a [i] 没有出现在 a [f [i-1][j], \dots, i-1] 中 \\
f [i-1][j], & 如果知识点 a [i] 出现在 a [f [i-1][j], \dots, i-1] 中
\end{cases}
$$

于是问题转换为，我们如何确定 $a [i]$ 有没有在指定指定区域中出现。这个问题比较简单，我们记录一个数组 $bck [i]$ 表示当我们遍历到 $i$ 时，$a [i]$ 上次出现的位置 。只要判断 $bck [i]$ 与 $f [i-1][j]$ 的关系就好了。

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define MAXN 600010
#define MAXM 32
#define MAXV 1000010
#define MOD 998244353
typedef long long LL;

using namespace std;

int T;
int n, m, k;

int num;
LL a[MAXN];
LL c[MAXN];


LL cost[MAXN];
LL cnt[MAXN];
int f[MAXN][MAXM];

int last[MAXV];
int bck[MAXN];      // bck[i] 表示 a[i] 病毒上次出现的下标

int main()
{
    scanf("%d", &T);
    while(T--)
    {

        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%lld", a+i);
            last[a[i]] = 0;
        }

        for(int i=1; i<=n ;i++)
        {
            bck[i] = last[a[i]];
            last[a[i]] = i;
        }

        scanf("%d%lld", &m, &c[0]);
        for(int i=1; i<=m; i++)
            scanf("%lld", c+i);

        f[1][0] = 1;
        f[1][1] = 0;

        for(int i=2; i<=n; i++)
        {
            f[i][0] = i;
            for(int k=1; k<=m; k++)
            {
                if(bck[i] <= f[i-1][k])
                    f[i][k] = f[i-1][k-1];
                else
                    f[i][k] = f[i-1][k];
            }
        }

        cost[0] = 0;
        cnt[0] = 1;

        for(int i=1; i<=n; i++)
        {
            // 通用
            cost[i] = cost[i-1]+c[0];
            cnt[i] = cnt[i-1];

            for(int j=1; j<=min(m, i); j++)
            {
                int l = f[i][j];

                if(cost[i] > cost[l]+c[j])
                {
                    cost[i] = cost[l]+c[j];
                    cnt[i] = cnt[l];
                }
                else if(cost[i] == cost[l]+c[j])
                {
                    cnt[i] = (cnt[i]+cnt[l])%MOD;
                }

                if(l == 0)
                    break;
            }
        }

        printf("%lld %lld\n",cost[n], cnt[n]);

    }
    return 0;
}