【膜拜】MYJ
WeLikeStudying · · 题解
- MYJ 是我们的红太阳，让我们一起赞美 MYJ 吧。
题意
- 题面。
- 有
m 个对于长度为n 的序列a 的估价函数f_i=[\min_{k=l_i}^{r_i}a_k\le c_i]\cdot \min_{k=l_i}^{r_i}a_k 。 - 构造方案，最大化：
\sum_{i=1}^mf_i -
分析
- 不愧是 MYJ 大奆佬的题目，蒟蒻一看就不会了。
- MYJ 说，要简化问题：所以我们可以发现一个简单的信息，所有的
a_i 应该都是c_i 中的一个，否则显然可以使得估价函数的值变大，所以5\times 10^5 变成了4000 。 - MYJ 说，要学会变换：所以我们假设
f(l,r) 为使得l\le l_i,r_i\le r 的所有估价函数的和最大的安排，来思考它的最优子结构性质。 - 让我们任意选定一个
g 作为[l,r] 的中点并强行让它为最小值，那么所有经过g 的区间就全部处理完毕了，问题被分为两个互相独立的区间。 - 所以我们设
f(l,r,k) 为设定让a_l 到a_r 大于等于c_k ，处理完被[l,r] 区间覆盖的估价函数的最优方案。 - 聪明地转移，时间复杂度是
O(n^3m) ，空间复杂度是O(n^2m) ，聪明地剪枝，复杂度绝对卡不满，对于输出方案的问题，我们显然可以在算出最优的答案后轻易地倒推。 - 所以我们就成功地水过了这道题：真是让人感到无尽地愉悦啊！代码实现，比记忆化搜索可能会慢一点。
- 我觉得这种方法还是有启发性的吧，不愧是 MYJ 啊！