单调队列和简单斜率优化小结

我一直觉得单调队列和斜率优化都是很难理解的东西，事实上我也确实理解了很久。去年省选集训的时候学过一次，没学会；今年NOIP集训的时候又做了一题，还是没什么感觉；NOIP完了，又做了几题单调队列，还是看题解的……还好今年省选集训的时候还是弄懂了。

其实斜率优化之所以和单调队列关系这么大，原因还是大部分题目斜率优化能保证决策的单调性，不要的就扔掉，所以就用了单调队列了。既然单调队列这么重要，所以今年开始练斜率优化的时候我就先打了几题单调队列。

参考资料

单调队列

单调队列就是一定要想清楚，到底我什么时候该把头扔掉（一般删头是因为不满足题目要求，或者不够优并且不会在后面变优），到底我把什么样的尾扔掉（尾都是备胎，一般扔掉是因为当前尾由于当前状态的出现而变得一文不值，连当备胎的机会都没有）。

另外还有一个非常严重的问题，就是先维护队尾还是先维护队头。这个得取决于具体的DP方程，如果当前决策能选到自己的话，那就得先维护队尾再维护队头，最后把头那个决策拿出来算DP值。

斜率优化

因为斜率不单调的斜率优化我还没做出来（o(╯□╰)o），所以先不讨论斜率不单调的斜率优化。

总的来说，斜率优化就是这样：求最小值，维护下凸壳；求最大值，维护上凸壳。画个图还是比较容易理解的。转化出xy以后就变成模板了。

单调队列例题

  • hdu3401
  • hdu3530
  • poj3017
  • poj3245 (二分第三问答案，预处理第一问，然后把poj3017复制过来就对了)

斜率优化例题

  • poj2018
  • hdu2993
  • bzoj1010
  • hdu3507
  • bzoj1911
  • bzoj1096
  • hdu2829（二维的看起来很吓人，但是决策那维还是一维的）

poj3245 代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 50002;
const long long INF = 0x3F3F3F3F3F3F3F3FLL;
int n, _st, Q[MAXN], a[MAXN], b[MAXN], p[MAXN], q[MAXN];
long long m, limit, lef, rig, _x, f[MAXN], s[MAXN*4], sum[MAXN];
void _modify(const int p, const int lef, const int rig)
{
  if (lef == rig)
    { s[p] = _x; return; }
  const int mid = (lef+rig)/2;
  if (_st <= mid) _modify(p*2, lef, mid);
  else _modify(p*2+1, mid+1, rig);
  s[p] = std::min(s[p*2], s[p*2+1]);
}
inline void Modify(const int pos, const long long x)
{
  _st = pos, _x = x;
  _modify(1, 1, n+1);
}
long long check(const long long m)
{
  memset(s, 0x3F, sizeof(s));
  int head = 1, tail = 0, lef = 0;
  for (int i = 1; i <= n; ++i)
  {
    while (sum[i]-sum[lef] > m) ++lef;
    while (head <= tail && Q[head] < lef) Modify(head++, INF);
    while (head <= tail && a[i] >= a[Q[tail]]) Modify(tail--, INF);
    Q[++tail] = i;
    if (head < tail)
      Modify(tail-1, f[Q[tail-1]]+a[i]);
    f[i] = std::min(f[lef]+a[Q[head]], s[1]);
  }
  return f[n];
}
inline bool cmp(const int lhs, const int rhs) { return b[lhs] < b[rhs]; }
void prepare()
{
  std::sort(p+1, p+1+n, cmp);
  for (int j = 1, i = n; i > 0; --i)
    while (j <= n && b[p[j]] <= a[i])
      q[p[j++]] = i;
  int j = 1;
  for (int i = 1, lef, rig; i <= n; i = lef, ++j)
  {
    a[j] = a[i], b[j] = b[i];
    for (lef = i+1, rig = std::max(q[i], i); lef <= rig; ++lef)
    {
      b[j] += b[lef];
      a[j] = std::max(a[j], a[lef]);
      rig = std::max(rig, q[lef]);
    }
  }
  n = j-1;
}
int main()
{
  scanf("%d%I64d", &n, &limit);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d%d", a+i, b+i);
    p[i] = q[i] = i;
  }
  prepare();
  for (int i = 1; i <= n; ++i)
  {
    lef = std::max(lef, static_cast<long long>(b[i]));
    sum[i] = sum[i-1] + b[i];
  }
  --lef, rig = sum[n];
  while (rig-lef > 1)
  {
    const long long mid = (lef+rig)/2;
    if (check(mid) <= limit)
      rig = mid;
    else
      lef = mid;
  }
  printf("%I64d", rig);
}

bzoj1010 代码（可以当模板了）

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

#include <cstdio>
#include <algorithm>

const int MAXN = 50001;
int n, l, Q[MAXN];
long long f[MAXN], s[MAXN];
inline long long sqr(const long long x) { return x*x; }
inline long long X(const int j) { return s[j] + j; }
inline long long Y(const int j) { return f[j] + sqr(X(j)); }
inline long long dx(const int x1, const int x2) { return X(x2)-X(x1); }
inline long long dy(const int x1, const int x2) { return Y(x2)-Y(x1); }
int main()
{
  scanf("%d%d", &n, &l);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%lld", s+i);
    s[i] += s[i-1];
  }
  for (int head = 0, tail = 0, i = 1; i <= n; ++i)
  {
    const long long A = s[i] + i - 1 - l;
    while (head < tail && -2*A*X(Q[head])+Y(Q[head]) >= -2*A*X(Q[head+1])+Y(Q[head+1])) ++head;
    f[i] = -2*A*X(Q[head])+Y(Q[head]) + sqr(A);
    while (head < tail && dy(Q[tail-1], Q[tail])*dx(Q[tail], i) >= dx(Q[tail-1], Q[tail])*dy(Q[tail], i)) --tail;
    Q[++tail] = i;
  }
  printf("%lld", f[n]);
}

hdu2829 代码

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

#include <cstdio>
#include <algorithm>

const int MAXN = 1001;
int n, m;
long long c[MAXN], s[MAXN], a[MAXN], Q[MAXN], f[MAXN][MAXN];
inline long long sqr(const long long x) { return x*x; }
inline long long X(const int k) { return s[k]; }
inline long long Y(const int j, const int k) { return f[k][j-1] - c[k] + sqr(s[k]); }
inline long long dx(const int x1, const int x2) { return X(x2) - X(x1); }
inline long long dy(const int j, const int x1, const int x2) { return Y(j, x2) - Y(j, x1); }
inline long long calc(const int i, const int j, const int k) { return Y(j, k) - s[i]*X(k); }
int main()
{
  while (scanf("%d%d", &n, &m) != EOF && (n || m))
  {
    for (int i = 1; i <= n; ++i)
      scanf("%I64d", a+i);
    for (int i = 1; i <= n; ++i)
    {
      s[i] = s[i-1]+a[i];
      c[i] = c[i-1];
      for (int j = 1; j < i; ++j)
        c[i] += a[i]*a[j];
      f[i][0] = c[i];
    }
    for (int j = 1; j <= m; ++j)
      for (int i = 1, head = 0, tail = 0; i <= n; ++i)
      {
        while (head < tail && calc(i, j, Q[head]) >= calc(i, j, Q[head+1])) ++head;
        f[i][j] = calc(i, j, Q[head]) + c[i];
        while (head < tail && dy(j, Q[tail-1], Q[tail])*dx(Q[tail], i) >= dx(Q[tail-1], Q[tail])*dy(j, Q[tail], i)) --tail;
        Q[++tail] = i;
      }
    printf("%I64d\n", f[n][m]);
  }
}

Comments