[POJ3017]Cut the Sequence

给定a[]，求一种划分方法，使得每段的和不大于M，并且每段的最大值的和最小。

这题是好题，一年内我做了三遍，前两遍都是看题解，不断的改程序，最后碰运气过的。第三遍终于是自己做出来的。

前两次看到题目中最大值最小，总是会想到二分去，第三次一想，不对，如果能验证答案的话那也能直接求出答案。所以这题的正解还是动规。

f[i] = min{ f[j] + max{a[j+1]..a[i]} } (sum[i]-sum[j] <= M)

朴素方程是O(n^2)的，下面考虑优化。

区间最大值，而且还有和的限制，显然RMQ不管用了，然而单调队列正好就是处理这种事情的。保存一个单调递减的单调队列，那么我们取出来队头就是区间的最大值了。

假设我们队列里面的元素x的位置和值分别是Q[x].pos和Q[x].value，那么对于当前的最优决策只能是：min{ f[Q[x-1].pos] + Q[x].value }，因为从Q[x-1].pos到i这一段的最大值都是Q[x].value。

如果要科学一点地解释的话，那就要证明：如果一个点k能成为最优决策，当且仅当a[k] > max{a[k+1]..a[i]}。原因也很简单，如果a[k]不比后面的值大的话，那么我们不如在k前面找一个x，使得max{a[x+1]..a[i]} = max{a[k+1]..a[i]}，又因为人类已经无法阻挡f[i]递增的趋势了，注意看DP方程，会发现f[x] <= f[k]，而后面那项又是相等的，所以k肯定不如x优。

下面我们该考虑如何得到最优决策，毕竟我们只是保证了队列里面的数是递减的，只是去掉了一些无用的决策，还是得对队列里面的每个元素计算 min{ f[Q[x-1].pos] + Q[x].value }。容易发现，这个值插进队列里面以后是固定的（跟i无关），所以随便拿一种O(log n)的数据结构都可以维护这个的最大值。一般人回去打平衡树，我比较喜欢线段树，所以就用队列下标建了一棵线段树。另外堆也是可以的，如果用一个bool数组表示当前值是否被删，然后配合std::priority_queue<>也是可以搞的（就跟Dijkstra + Heap一样）。

程序如下：

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

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

const int MAXN = 100002;
const long long INF = 0x3F3F3F3F3F3F3F3FLL;
int n, _st, Q[MAXN], a[MAXN];
long long m, _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);
}
int main()
{
  memset(s, 0x3F, sizeof(s));
  scanf("%d%I64d", &n, &m);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", a+i);
    if (a[i] > m)
      { printf("-1"); return 0; }
    sum[i] = sum[i-1] + a[i];
  }
  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]);
  }
  printf("%I64d", f[n]);
}

Comments