题目描述

给定一段时间内股票的每日售价（正 16 位整数）。

你可以选择在任何一天购买股票。

每次你选择购买时，当前的股票价格必须严格低于你之前购买股票时的价格。

编写一个程序，确定你应该在哪些天购进股票，可以使得你能够购买股票的次数最大化。

输出最大买进股票次数以及可以达到最大买进次数的方案数。

如果两种方案的买入日序列不同，但是价格序列相同，则认为这是相同的方案（只计算一次）。

输入格式

第 1 行包含整数 $N$，表示给出的股票价格的天数。

第 2 至最后一行，共包含 $N$ 个整数，每行 10 个，最后一行可能不够 10 个，表示 $N$ 天的股票价格。

同一行数之间用空格隔开。

输出格式

输出占一行，包含两个整数，分别表示最大买进股票次数以及可以达到最大买进次数的方案数。

样例1

12
68 69 54 64 68 64 70 67 78 62
98 87

4 2

样例2

5
4 3 2 1 1

4 1

样例解释

样例1

股票价格序列（天数 1 到 12）： 68, 69, 54, 64, 68, 64, 70, 67, 78, 62, 98, 87

要求每次购买时价格严格低于之前购买的价格。

最长下降子序列

这相当于求最长严格下降子序列的长度。

计算：

• 最长严格下降子序列长度为 4。 例如：69, 68, 64, 62 （第2,5,6,10天） 或者：69, 68, 64, 62 （第2,5,8,10天）？但第8天价格67，不是64。 实际上，价格序列不同的才算不同方案，价格序列相同但天数不同视为相同方案。

题目规定：如果两种方案的买入日序列不同，但是价格序列相同，则认为这是相同的方案（只计算一次）。所以我们只关心价格序列，不关心具体是哪一天买的。

因此，我们需要求最长严格下降子序列的长度，以及不同的最长严格下降子序列的个数（只按价格序列区分）。

方案数

长度为 4 的严格下降子序列价格序列可能有两个：

1. 69, 68, 64, 62
2. 70, 67, 62, ? 但 62 之后没有更小的，长度不够。 实际上，可能还有 70, 67, 62, ? 没有。

我们枚举可能的最长下降子序列：

• 从 69 开始：69, 68, 64, 62
• 从 70 开始：70, 67, 62, ? 之后没有比 62 小的，长度只有 3。
• 从 68（第一天）开始：68, 64, 62, ? 长度 3。
• 从 68（第五天）开始：68, 64, 62, ? 长度 3。
• 从 64（第四天）开始：64, 62, ? 长度 2。
• 从 64（第六天）开始：64, 62, ? 长度 2。
• 从 54 开始：54, ? 后面没有更小的。

所以只有一种价格序列 69,68,64,62 能达到长度 4。但输出是 2，说明有两种不同的价格序列？我们再仔细看。

可能还有 69,67,62,? 但 67 之后 62，之后没有更小的。 70,67,62,? 不够长。 78,62,? 不够长。

也许有 69,64,62,? 但 64 之后 62，再之后没有更小的，长度 3。

所以为什么输出 2？可能是因为相同的价格序列但不同的天数组合被视为相同，所以只算一种，那么方案数应该是 1，但输出是 2。

仔细读题：“如果两种方案的买入日序列不同，但是价格序列相同，则认为这是相同的方案（只计算一次）。” 这意味着我们只按价格序列来区分方案，所以如果价格序列相同，即使在不同天购买也算一种。

那么样例1的输出 4 2 说明有两种不同的价格序列能达到长度 4。

我们找出所有长度为 4 的严格下降子序列的价格序列：

价格列表（带天数）： 1:68, 2:69, 3:54, 4:64, 5:68, 6:64, 7:70, 8:67, 9:78, 10:62, 11:98, 12:87

严格下降子序列：

• 2(69) -> 5(68) -> 6(64) -> 10(62) 价格序列：69,68,64,62
• 2(69) -> 5(68) -> 8(67) -> 10(62) 价格序列：69,68,67,62 ❌ 67 不是严格低于 68？67<68，是严格下降，所以这是不同的价格序列。 检查：69,68,67,62 是严格下降的。 所以有两种不同的价格序列：69,68,64,62 和 69,68,67,62。 输出 4 2 符合。

样例2

价格序列：4,3,2,1,1

严格下降子序列：由于有重复的 1，但要求严格下降，所以最长长度为 4：4,3,2,1（取第一个1）。 价格序列只有一种：4,3,2,1。 所以输出 4 1。

数据范围

• $1 \le N \le 5000$
• 价格是正整数（16位整数，但不超过 int 范围）
• 答案不超过 int 范围

算法分析

问题转化

我们需要求：

1. 最长严格下降子序列的长度 $L$。
2. 长度为 $L$ 的严格下降子序列的个数（不同的价格序列）。

注意：如果相同的价格值在不同位置出现，但价格序列相同，视为同一种方案。例如价格序列 3,2,1 和 3,2,1（来自不同位置）算一种。

因此，对于相同的价格值，我们需要去重：如果有多个相同的价格值，它们形成的下降子序列如果价格序列相同，则只算一次。

动态规划

设 $f[i]$ 表示以第 $i$ 个价格结尾的最长严格下降子序列的长度。 设 $g[i]$ 表示以第 $i$ 个价格结尾的最长严格下降子序列的个数（按价格序列去重）。

转移： $f[i] = \max_{j < i, a[j] > a[i]} f[j] + 1$（严格下降，所以前面的价格 $a[j]$ 必须大于 $a[i]$）。

$g[i]$ 的转移：所有满足 $j < i, a[j] > a[i]$ 且 $f[j] + 1 = f[i]$ 的 $j$，将 $g[j]$ 累加到 $g[i]$ 上。

但需要去重：如果存在 $j_1 < j_2 < i$，$a[j_1] = a[j_2]$，且 $f[j_1] = f[j_2]$，那么它们贡献的下降子序列可能会重复（因为价格序列相同）。例如，价格序列中有多个相同的值，它们可能会产生相同的价格序列。

去重方法： 在累加 $g[j]$ 时，对于相同的价格 $a[j]$，我们只取最后一个满足条件的 $j$（即离 $i$ 最近的那个）的贡献，因为之前相同价格的 $j$ 产生的序列会被后面的 $j$ 包含（由于是严格下降，相同价格不能连续，但可能在不同位置，如果 $a[j_1]=a[j_2]$，且 $j_1<j_2$，那么以 $j_2$ 结尾的序列可以通过 $j_1$ 得到相同的价格序列，但 $j_2$ 的序列可能更长？由于价格相同，$f[j_1]$ 可能等于 $f[j_2]$，但 $j_2$ 更靠后，其序列可能包含更多元素？不对，因为价格相同，以 $j_1$ 结尾和以 $j_2$ 结尾的最长下降子序列长度可能相同，但序列内容可能不同（前面的元素不同）。但题目要求价格序列相同则视为同一种，所以如果 $a[j_1]=a[j_2]$，且它们前面接的元素不同，价格序列可能不同，不能简单去重。

实际上，去重应该在计算方案数时，对于相同的价格序列只算一次。由于价格序列是由值构成的，如果有两个位置 $j_1$ 和 $j_2$，$a[j_1]=a[j_2]$，且 $f[j_1]=f[j_2]$，那么以 $j_1$ 结尾和以 $j_2$ 结尾的最长下降子序列可能不同（因为前面的元素不同），但价格序列可能相同也可能不同。例如序列 3,2,3,1，以第一个 3 结尾的长度为 1，以第二个 3 结尾的长度也为 1，但价格序列都是 3，相同。如果前面元素不同，如 4,3,2,3，以第一个 3 结尾的序列可能是 4,3，以第二个 3 结尾的序列可能是 2,3，价格序列不同。

因此，不能简单地按相同价格去重。

一个正确的方法是：在计算 $g[i]$ 时，对于所有 $j < i, a[j] > a[i]$ 且 $f[j]+1 = f[i]$，我们累加 $g[j]$，但需要避免同一价格序列被多次计算。由于价格序列是由值构成的，如果两个不同的 $j$ 产生了相同的价格序列，那么这两个序列的最后一个值相同（都是 $a[j]$），且前面的序列也相同。这意味着存在 $j_1 < j_2$，$a[j_1]=a[j_2]$，且它们对应的最长下降子序列的前缀相同（即 $f[j_1]=f[j_2]$ 且从某个 $k$ 转移过来的序列相同）。这很难处理。

另一种思路：将问题转化为求最长严格下降子序列的长度和方案数，其中方案按值序列去重。可以使用 DP 加去重技巧：对于每个位置 $i$，我们记录以它结尾的最长下降子序列的长度和方案数，并且在转移时，如果遇到相同的价格，只从最近的一个转移过来？但这样会漏掉一些方案。

实际上，这是一个经典问题：求最长下降子序列的个数（去重）。常见解法是 DP 并用一个集合去重：对于每个长度 $len$，维护一个字典，键为序列的哈希或最后几个值，但复杂度高。

由于 $N \le 5000$，我们可以用 $O(N^2)$ 的 DP。

具体做法：

• 首先计算 $f[i]$。
• 然后计算 $g[i]$：$g[i] = \sum_{j < i, a[j] > a[i], f[j]+1 = f[i]} g[j]$。
• 去重：如果存在 $j_1 < j_2 < i$，$a[j_1] = a[j_2]$，且 $f[j_1] = f[j_2]$，那么以 $j_2$ 结尾的序列可能包含以 $j_1$ 结尾的序列。为了去重，我们可以规定：对于相同的价格 $v$，当我们在计算 $g[i]$ 时，只考虑最后一个 $j$ 满足 $a[j] = v$ 且 $f[j]$ 为某个值。但这样可能会漏掉一些方案，因为 $j_1$ 和 $j_2$ 可能从不同的前驱转移过来，形成不同的序列。

更好的方法是：在计算 $g[i]$ 时，对于每个 $j$，检查是否存在 $k$ 满足 $j < k < i$，$a[k] = a[j]$，且 $f[k] = f[j]$，如果有，则 $j$ 的贡献已经被 $k$ 覆盖，跳过 $j$。这是因为对于相同的价格，位置靠后的 $k$ 可以覆盖位置靠前的 $j$ 的所有方案（因为 $k$ 之后可以接的元素，$j$ 之后也可以接，且序列值相同）。但需要注意：$j$ 和 $k$ 之前的历史可能不同，但最终形成的以 $i$ 结尾的序列，如果 $j$ 和 $k$ 的价格相同，且 $f[j]=f[k]$，那么从 $j$ 转移过来的序列和从 $k$ 转移过来的序列，在加入 $a[i]$ 后，价格序列是相同的（因为 $a[j]=a[k]$，$a[i]$ 相同）。因此，我们只需要保留靠后的那个 $j$ 的贡献，避免重复。

因此，算法如下：

1. 计算 $f[i]$。
2. 计算 $g[i]$：枚举 $j$ 从 $i-1$ downto 1，如果 $a[j] > a[i]$ 且 $f[j]+1 = f[i]$，则将 $g[j]$ 加入 $g[i]$，同时如果遇到 $a[j]$ 已经出现过（即之前有 $k$ 满足 $a[k]=a[j]$ 且 $f[k]=f[j]$），则跳过（因为已经计算过）。 实现时，可以用一个数组 $last[v]$ 记录对于价格 $v$，当前已经考虑过的 $j$ 中最大的 $j$ 的 $f[j]$ 值？但 $f[j]$ 可能不同，所以需要用 $last[v][len]$ 记录对于价格 $v$ 和长度 $len$，是否已经计算过。

由于价格范围较大（16位整数），但 $N$ 只有 5000，我们可以离散化价格。

最终算法

1. 读入价格数组 $a[1..N]$。
2. 计算 $f[i]$：$f[i] = 1$，对于每个 $i$，枚举 $j < i$，如果 $a[j] > a[i]$，则 $f[i] = \max(f[i], f[j]+1)$。
3. 计算 $g[i]$：
   • 初始化 $g[i] = 0$。
   • 用一个数组 $used$ 记录对于每个价格值，是否已经在该轮计算中使用过（避免重复）。
   • 从 $j = i-1$ downto 1：
     • 如果 $a[j] > a[i]$ 且 $f[j] + 1 == f[i]$ 且 $used[a[j]]$ 为 false，则 $g[i] += g[j]$，并标记 $used[a[j]] = true$。
   • 如果 $g[i] == 0$，则 $g[i] = 1$（表示以 $i$ 结尾的序列本身）。
4. 求全局最长长度 $L = \max f[i]$。
5. 求方案数：对于所有 $f[i] = L$ 的 $i$，累加 $g[i]$，同时去重：同样用 $used$ 数组，对于每个价格 $a[i]$，只加一次。

复杂度

• 计算 $f$：$O(N^2)$。
• 计算 $g$：对于每个 $i$，枚举 $j$，$O(N^2)$。
• 总复杂度 $O(N^2)$，$N=5000$ 时 $25\times 10^6$，可以接受。

样例验证

样例1

通过算法可得 $L=4$，方案数 2，符合输出。

样例2

$L=4$，方案数 1，符合。

总结

本题要求最长严格下降子序列的长度和不同价格序列的方案数，关键在于去重。采用 $O(N^2)$ DP 并利用价格值去重即可。