CF1793E Velepin and Marketing

个人思路：

从小到大排序，因为一定先满足小的，再满足大的。

分组时，我们发现，同一组内的数在排序后的序列内连续，这样更优。因为（不会证）。

我们预处理出对于每个出书数量的答案，查询时直接输出即可。我们发现出书数量越多，满足人数越少，但是不能递推。

如果求出满足前 \(i\) 个时的最多出书数量 \(t_i\)，我们就可以反推答案。但是也不能递推。

状态：\(dp_i\) 表示满足前 \(i\) 个时，前 \(i\) 个数最多分为多少组。

转移：

当 \(i < a_i\) 时，显然不能满足。此时 \(dp_i = 0\)。

否则，\(dp_i = \max\limits_{1\le j<i-a_i} dp_j + 1\)，我们只需要划分至少 \(a_i\) 个数与 \(i\) 一组，剩下的数尽量多分。

答案：

对于 \(i < a_i\) 时，满足前 \(i\) 个时的最大出书数量 \(t_i\) 即为 \(n - a_i + 1\)，即前 \(a_i\) 个分一组，剩余一个一组。

否则，满足前 \(i\) 个时的最大出书数量 \(t_i\) 即为 \(dp_i + n - i\)，即前 \(i\) 个分 \(dp_i\) 组，剩余一个一组。

显然，对于 \(i < a_i\) 时，这个答案不一定最优，因为可以和后面的分成一组。于是，我们从右往左遍历，\(t_i \leftarrow \max(t_i, t_{i+1})\)。

反推答案，对于 \(t_{i+1} < p \le t_i\)，\(ans_p = i\)。

然后稀里糊涂地过去了。

巴特西

CF1793E Velepin and Marketing

最新文章

热门文章