P7804 [JOI Open 2021] 决算报告 / Financial Report

**警告：滥用本题评测将被封号。**

有一个长度为 $N$ 的序列 $A_i$，定义函数 $f(m,p_1,p_2,\cdots,p_m)$ 的值为满足： $$\max\limits_{j=1}^{i-1}\{A_{p_j}\} < A_{p_i}$$ 的 $p_i$ 的个数，当 $i=1$ 时，我们假设上面这个不等式是恒成立的。 给定一个整数 $D$，求一个序列 $p_i$ 满足： - $1 \le m \le N$； - $p_m=N$； - $p_i

第一行两个整数 $N,D$，意义如题面所述。 第二行 $N$ 个整数 $A_i$ 代表给定的序列。

一行一个整数代表 $f$ 函数的最大值。

#### 样例 1 解释 一共有 $7$ 种可能的情况： - $p_i=\{1,2,3,4,5,6,7\}$，$f(7,1,2,3,4,5,6,7)=2$； - $p_i=\{2,3,4,5,6,7\}$，$f(6,2,3,4,5,6,7)=1$； - $p_i=\{3,4,5,6,7\}$，$f(5,3,4,5,6,7)=1$； - $p_i=\{4,5,6,7\}$，$f(4,4,5,6,7)=3$； - $p_i=\{5,6,7\}$，$f(3,5,6,7)=2$； - $p_i=\{6,7\}$，$f(2,6,7)=1$； - $p_i=\{7\}$，$f(1,7)=1$。 最大值为 $3$。 #### 样例 2 解释 最优的 $p_i=\{1,3,4,5,6\}$，对应的 $A_i=\{100,200,400,600,300\}$，$f$ 函数值为 $4$。 #### 样例 3 解释 最优的方式有多种，其中一种是 $p_i=\{1,3,5,6,8,9,11\}$，对应的 $A_i=\{ 1, 4, 2, 4, 5, 7, 3\}$，$f$ 函数值为 $4$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（14 pts）：$N \le 20$； - Subtask 2（14 pts）：$N \le 400$； - Subtask 3（20 pts）：$N \le 7000$； - Subtask 4（12 pts）：$D=1$； - Subtask 5（5 pts）：$D=N$； - Subtask 6（35 pts）：无特殊限制。 对于 $100\%$ 的数据： - $1 \le N \le 3 \times 10^5$； - $1 \le D \le N$； - $0 \le A_i \le 10^9$。 #### 说明 翻译自 [JOI 2020 / 2021 Open Contest B Financial Report](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2021/financial/2021-open-financial-statement-en.pdf)。