CF1793E Velepin and Marketing
阅读原文时间:2023年07月08日阅读:3

个人思路:

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

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

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

如果求出满足前 \(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\)。

然后稀里糊涂地过去了。

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章