斜率优化 dp 模板。
令 $c_i=\sum\limits_{j=1}^iC_j$,$t_i=\sum\limits_{j=1}^iT_j$(前缀和),则原 dp 方程为:$f_i=\min\limits_{j=0}^{i-1}(f_j+S(c_n-c_j)+t_i(c_i-c_j))$
考虑优化掉枚举取 $\min$ 的过程:
首先,我们分析对于 $j,k(k<j)$ 两个位置,我们什么时候一定不会用 $k$ 作为决策点更新$f_i$,即 $j$ 的答案恒比 $k$ 优,
此时 $f_j+S(c_n-c_j)+t_i(c_i-c_j)<f_k+S(c_n-c_k)+t_i(c_i-c_k)$,化简得 $\cfrac{f_j-f_k}{c_j-c_k}<S+t_i$;
在这个式子中,若我们把 $(c_j,f_j)$ 和 $(c_k,f_k)$ 看作代表 $j,k$ 的两个点,则 $\cfrac{f_j-f_k}{c_j-c_k}$ 为过两点的直线的斜率;因为 $T_i$ 为正整数,所以 $S+t_i$ 是单调递增的;
由此结合画图可以发现,只有在下凸壳右半部分上的点才有可能为后续 $f_i$ 更新,其他的点一定没有在下凸壳右半部分上的点优,所以我们可以维护一个队头最小的单调队列,其中相邻的两个点的直线斜率都是递增的。
接着,我们考虑如何快速获取当前最佳点,对原方程化简移项得 $f_j=(s+t_i)c_j+f_i-Sc_n-t_ic_i$;
若将 $f_j$ 看作 $y=kx+b$ 中的 $y$,$(S+t_i)$ 看作 $k$,$c_j$ 看作 $x$,$f_i-Sc_n-t_ic_i$ 看作 $b$,则这就是一个一次函数的解析式;
想要让 $f_i$ 最小,也就是让 $b$ 最小,也就是要使这个一次函数的截距最小;
我们选择某个 $j$ 作为 $i$ 的决策点,本质上就是令斜率为 $S+t_i$ 的直线过点 $j$,算出关于截距的答案;
而显然,使截距最小的点,就是斜率为 $S+t_i$ 下边往上平移碰到的凸壳上的第一个点,若这个点和它前后的点的连线的斜率分别为 $k_1,k_2$,不难发现有 $k_1\leq S+t_i < k_2$;
所以,每次遍历到新的点时,我们把从队头开始所有前后两点连线斜率小于 $S+t_i$ 的点弹出,剩下队头的点就是最佳决策点;后续维护单调队列时,把队尾所有 大于当前点与队尾点连线的斜率 的斜率弹出再插入自己即可。
总时间复杂度 $O(n)$。
#include <deque>
#include <iostream>
#define int long long
#define front q.front()
#define back q.back()
#define sfront *(q.begin() + 1)
#define sback *(q.rbegin() + 1)
using namespace std;
const int N = 3e5 + 10;
int n, s;
int t[N], c[N];
int f[N];
deque<int> q;
inline void speedup()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
signed main()
{
speedup();
cin >> n >> s;
for (int i = 1; i <= n; i++)
cin >> t[i] >> c[i];
for (int i = 1; i <= n; i++)
t[i] += t[i - 1], c[i] += c[i - 1];
f[0] = 0;
q.push_back(0);
for (int i = 1; i <= n; i++)
{
while (q.size() > 1 && f[sfront] - f[front] <= (t[i] + s) * (c[sfront] - c[front]))
q.pop_front();
f[i] = f[front] + s * (c[n] - c[front]) + t[i] * (c[i] - c[front]);
while (q.size() > 1 && (f[i] - f[back]) * (c[back] - c[sback]) <= (f[back] - f[sback]) * (c[i] - c[back]))
q.pop_back();
q.push_back(i);
}
cout << f[n] << endl;
return 0;
}
deque为啥会在洛谷 只能拿60分