P5785 [SDOI2012]任务安排
与另一道任务安排唯一不一样的地方是可能存在 $t _ i < 0$ ，这意味着斜率不再具有单调性。因此单调队列中斜率小于 $k$ 的不再能直接删除。而凸包中的边的斜率是有单调性的，所以我们二分这些边，找到第一条相切的边。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <iostream>
#include <cstdio>
#include <climits>
#define inf INT_MAX
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n;
int hd = 1, tl = 0;
LL q[N];
LL s, st[N], sc[N], f[N];
int get (int i, int k)
{
int l = hd, r = tl;
while (l < r)
{
int mid = l + r>> 1;
if (f[q[mid + 1]] - f[q[mid]] <= k * (sc[q[mid + 1]] - sc[q[mid]]))
l = mid + 1;
else
r = mid;
}
return q[l];
}
int main ()
{
cin >> n >> s;
for (int i = 1; i <= n; i++)
{
LL a, b;
cin >> a >> b;
st[i] = st[i - 1] + a;
sc[i] = sc[i - 1] + b;
}
for (int i = 1; i <= n; i++)
f[i] = inf;
q[++tl] = 0;
for (int i = 1; i <= n; i++)
{
int p = get(i, s + st[i]);
f[i] = f[p] - (s + st[i]) * sc[p] + st[i] * sc[i] + s * sc[n];
while (hd < tl && (f[q[tl]] - f[q[tl - 1]]) * (sc[i] - sc[q[tl]]) >= (f[i] - f[q[tl]]) * (sc[q[tl]] - sc[q[tl - 1]]))
tl--;
q[++tl] = i;
}
cout << f[n];
return 0;
}
|