松松的题目集

发表于 2022-09-29 更新于 2025-03-05 分类于 ACM ， DP 本文字数： 3.8k 阅读时长 ≈ 7 分钟

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

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

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

输入格式

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

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

第二行输入 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ ，表示每个题目考察的知识点。

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

第四行输入 $(m + 1)$ 个整数 $c_{0}, c_{1}, \dots, c_{m} (1 \leq c_{0} < c_{1} < \dots < c_{m} \leq 10^{9})$ ，其中 $c_{0}$ 表示使用做题方法一使用的时间， $c_{i}$ 表示使用大小为 $i$ 的小抄需要的时间。

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

输出格式

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

输入样例

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 \leq c_{0} < c_{1} < \dots < c_{m} \leq 10^{9}$
当我们使用小抄时，小抄中的知识点越多，则使用小抄花费的时间就严格越多。

思路

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

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

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 \leq 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]$ 有没有在指定指定区域中出现。这个问题比较简单，我们记录一个数组 $b c k [i]$ 表示当我们遍历到 $i$ 时， $a [i]$ 上次出现的位置。只要判断 $b c k [i]$ 与 $f [i - 1] [j]$ 的关系就好了。

代码

#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;
}