ISIJ 2019 Training Contest 1 Task D: Antimatter

题意

现在有 \(n\) 种实验，第 \(i\) 种消耗 \(c_i\) 个正物质，获得 \(l_i\sim r_i\) 中任意一个整数的反物质
如果你做完第 \(i\) 个实验，获得了 \(x\) 个反物质，那么可以获得 \(10^9x-c_i\) 的价值
你需要用一个容量为 \(m\) 的容器去保存生成的反物质，但是因为反物质非常危险，所以如果你当前有 \(x\) 个反物质，\(x+r_i>m\)，那么就不能做第 \(i\) 个实验，否则可能会出现严重的爆炸事故
你现在有无数个正物质，问你最多能获得多少价值

\(n\leq 100,m\leq 2\times 10^6\)
时间限制：2s
空间限制：128M

样例

input1:
1 17
4 6 10
output1:
11999999970

input2:
2 11
2 2 100
3 5 5
output2:
9999999890

题解

考虑一个显而易见的 dp，用 \(f[x]\) 表示拿到 \(x\) 个反物质时的最大价值

显然这个式子可以边做边维护一个ST表，直接解决问题
时间复杂度 \(\mathcal O(nm)\)，空间复杂度 \(\mathcal O(m\log m)\)，发现会 MLE
考虑进一步优化
我们考虑维护一个单调栈，在 \(x\) 的时候，我们更新 \(f[x+l_i]\) 的信息
我们做单调栈的同时可以把单调栈中的两个元素之间的元素全部连到靠右边的元素上，用并查集维护，这样 \(x\) 指向的元素就是 \([x,i]\) 中的最小值
这样我们直接调用 \(fa[x+l_i-r_i]\) 就可以找到最优转移位置了
时间复杂度 \(\mathcal O(na)\)，空间复杂度 \(\mathcal O(m)\)

一些有意思的题

原文：https://www.cnblogs.com/devout/p/14793537.html