P14597 [COCI 2025/2026 #2] 递增 / Rastući

本题满分 $110$。

给定长度为 $n$ 的序列 $a_1,\ldots,a_n$。 你可以进行如下的操作： > **操作** > > 设当前序列为 $[b_1,b_2,\ldots,b_m]$。 > > 选择 $1\le i\lt m$，将序列变为 $[b_1,b_2,\ldots,b_{i-1},b_i+b_{i+1},b_{i+2},\ldots,b_m]$。 > 目标是让 $a$ **不降**，即 $a_{i}\le a_{i+1}$。求出这样的 $a$ 的最大长度，并构造一个合法的 $a$。 本题中你可以获得部分分，详见「计分方式」。

第一行，一个正整数 $n$（$1\le n\le 5000$）。 第二行，$n$ 个正整数 $a_i$（$1\le a_i\le 10^9$）。

第一行，一个正整数 $m$，表示最终序列的最长长度。 第二行，$m$ 个正整数，表示操作后得到的序列。

### 样例解释 **样例一解释**：$[\textcolor{red}{3,2},6,3,3,8]\to [5,6,\textcolor{red}{3,3},8]\to [5,6,6,8]$。 ### 子任务 - $\text{Subtask 1 (10 pts)}$：$n\le 20$。 - $\text{Subtask 2 (15 pts)}$：$n\le 100,a_i\le 100$。 - $\text{Subtask 3 (20 pts)}$：$n\le 500$。 - $\text{Subtask 4 (25 pts)}$：$n\le 1000$。 - $\text{Subtask 5 (40 pts)}$：无额外限制。 ### 计分方式 正确回答第一行可以获得 $60\%$ 的分数。 在正确回答第一行的基础上正确回答第二行可以获得剩下 $40\%$ 的分数。 如果只想要获得 $60\%$ 的分数，也要在第二行输出 $m$ 个正整数，否则可能使得分出现偏差。