You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

46 lines
2.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300010;
LL t[N], c[N], f[N];
int q[N];
int main() {
int n, s;
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1];
int hh = 0, tt = 0; // 哨兵
for (int i = 1; i <= n; i++) {
/*
Q:为什么是 hh < tt ?
A:队列中最少有两个元素,才能考虑计算斜率,才能开始出队头
队列中一个元素,hh=0,tt=0
队列中两个元素,hh=0,tt=1 这样的情况下,保证了最少有一条边,才有斜率概念
(1) k=st[i]+S 所有数据是正数所以k是单调递增的
(2) k从下向上移动找到与点集的第一个交点必然在下凸壳上
(3) 在相交时,其实是与三个点组成的两条直线进行相交,设 a,b,c能够相交的必要因素是K_{a,b}<k<K_{b,c}
(4) 双向队列其实是一个单调上升的队列
(5) 双向队列中只保留斜率比当前ki大的下凸壳点集比ki斜率小的点以后也不会再使用在i入队列前删除掉
*/
// 队列头中的q[hh]其实是就是优解j,使得截距f[i]的值最小
// 要保证随时从队列头中取得的数是下凸壳中第一个从k=st[i]+s大的,原来有比k小于等于的点都可以剔除了
while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh++;
// Q:为什么在未入队列前更新?
// A: 因为i是在查询它的前序j,找到了使它最小的j就对了现在队列头中保存的就是使i最小的前序j,当然是放入队列前进行更新
f[i] = f[q[hh]] - (t[i] + s) * c[q[hh]] + c[i] * t[i] + s * c[n]; // 利用公式更新最优解
// 出队尾:现在凸包里记载的两个点之间斜率大于新加入值的清理掉
while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
q[++tt] = i;
}
// 输出
cout << f[n] << endl;
return 0;
}