牛客网 货物分组 – 题解

是的，又是一道考试时想出正解没有打出来的题目

货物分组 – 牛客网

根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：$$dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\}$$，初值有$dp(0, 0) = 0$，应求得$\min\limits_{j \in [1, n]} dp(n, j)$。

经过观察，我们发现，当我们钦定的分组方案中，第$1$到$k$组的货物重量分别为$s_{1 \dots k}$是，费用总和必然包含：$\sum\limits_{i=1}^{k}s_i \times i$，也就是 $$(s_1 + \dots + s_k) + (s_2 + \dots + s_k) + (s_3 + \dots + s_k) + \dots + s_k$$。这就说明，一旦我们决定要将区间$[l, r]$中的货物分成新的一组，那么总花费必然再次累积$\sum\limits_{i=l}^{n} a_i$。这就表明，我们根本没有必要关心当前区间具体分成第几组，因为总答案中必定会累积该组左端点及以后的货物的重量总和。

这种思想成为“代价提前计算”，或“更换维度计算贡献”。现在我们就有了改良后的状态：设$f(i)$为将第$i$件货物作为某一组的封口货物，对前$i$件货物包装的最小花费。写出转移：$$f(i) = \min\limits_{j \in [1, i)}{f(j) + \sum\limits_{p=j+1}^{n}a_p + \textrm{极差}\{a_t \mid t \in [j + 1, i]\}}$$

现在我们得到了一个优秀的$\mathrm{O}(n^2)$算法，可以获得$60$分。但我们进一步将转移式拆开来看，发现对于一个确定的$j$，有$f(j) + \sum\limits_{p=j+1}^{n}a_p$永不改变，变化的仅仅是$i$不同时的$\textrm{极差}\{a_t \mid t \in [j + 1, i]\}$罢了。所以，我们考虑有没有更聪明的办法，不必每次枚举$j$。

容易发现，极差随着区间长度的增加，是非严格单调递增的——因为只存在后来居上的最大值和最小值。同时我们观察，当我们钦定一个$j$，在完成$f(i)$的更新后（采用$\textrm{极差}\{a_t \mid t \in (j, i]\}$），则在更新$f(i + 1)$时，有三种可能：$(j, i + 1]$区间的最小值被更新；$(j, i + 1]$区间的最大值被更新；无法更新极值。前两者都会使得$\textrm{极差}\{a_t \mid t \in (j, i + 1]\}$较$\textrm{极差}\{a_t \mid t \in (j, i]\}$更大。同时我们发现，假设在区间$[1, i]$中首个较$a_{i+1}$大的数（后继）的位置为$p_0$，那么对于区间$[p_0 + 1, i + 1], [p_0 + 2, i + 1], \dots, [i + 1, i + 1]$（继承于区间$[p_0 + 1, i], [p_0 + 2, i], \dots, [i, i]$），它们的极差都会被$a_{i+1}$更新。同时，我们假设区间$[p_0 \dots p_1, i]$原本采取最大值$a_{p_1}$计算极差，且有$a_{i + 1} > a_{p_0} \geq a_{p_1}$，则有区间$[p_0 + 1, i + 1], [p_0 + 2, i + 1], \dots, [p_1, i + 1]$，极差都将增长$\Delta = a_{i+1}-a_{p1}$。所以考虑维护一个单调栈，分别保存单调递增/减的前缀区间的最值的位置。容易通过其记录的位置，更新对应区间的极差。

由于对于每一个$j$，只有区间$[j + 1, i]$的右端点在移动，则对于一个确定的$i$，区间$[j + 1, i]$和$f(j) + \sum\limits_{p=j+1}^{n}a_p$是一一绑定的，所以我们采用线段树进行极差的区间更新、单点修改、前缀最小值查询的各项操作。每更新一个$f(i)$，就将点$i$的初始值更新为$f(i) + \sum\limits_{p = i + 1}^n a_p$。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10; long long INF = 1ll<<62;
int n, W, a[N], tmp1, tmp2, minpos, mnv, mxv;
long long f[N], pre[N];
struct st {
	int s[N], r;
	void push (int x) { s[++r] = x; }
	int top () { return s[r]; }
	int size () { return r; }
	void pop () { s[r--] = 0; }
} mx, mn;
struct node {
	int l, r, tag;
	long long data;
} t[N<<2];

void build (int x, int l, int r) {
	t[x].l = l, t[x].r = r, t[x].data = INF, t[x].tag = 0;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build (x<<1, l, mid);
	build (x<<1|1, mid + 1, r);
}
void push_down (int x) {
	if (!t[x].tag) return;
	t[x<<1].tag += t[x].tag, t[x<<1].data += t[x].tag;
	t[x<<1|1].tag += t[x].tag, t[x<<1|1].data += t[x].tag;
	t[x].tag = 0;
}
void update_incre (int x, int L, int R, int delta) {
	if (t[x].l >= L && t[x].r <= R) {
		t[x].data += delta, t[x].tag += delta;
		return;
	}
	int mid = (t[x].l + t[x].r) >> 1;
	push_down (x);
	if (L <= mid) update_incre (x<<1, L, R, delta);
	if (R > mid) update_incre (x<<1|1, L, R, delta);
	t[x].data = min (t[x<<1].data, t[x<<1|1].data);
}
void update_sing (int x, int tar, long long num) {
	if (t[x].l == t[x].r && t[x].l == tar) {
		t[x].data = num, t[x].tag = 0;
		return;
	}
	int mid = (t[x].l + t[x].r) >> 1;
	push_down (x);
	if (tar <= mid) update_sing (x<<1, tar, num);
	else update_sing (x<<1|1, tar, num);
	t[x].data = min (t[x<<1].data, t[x<<1|1].data);
}
long long query (int x, int L, int R) {
	if (t[x].l >= L && t[x].r <= R)
		return t[x].data;
	int mid = (t[x].l + t[x].r) >> 1;
	long long res = INF;
	push_down (x);
	if (L <= mid) res = min (query (x<<1, L, R), res);
	if (R > mid) res = min (query (x<<1|1, L, R), res);
	return res;
}

int main () {
	/* C 吴秋实 */
//	freopen ("team.in", "r", stdin);
//	freopen ("team.out", "w", stdout);
	scanf ("%d%d", &n, &W);
	for (int i = 1; i <= n; ++i) {
		scanf ("%d", a + i);
		pre[i] = pre[i - 1] + a[i];
	}
	f[1] = pre[n];
	build (1, 1, n); 
	update_sing (1, 1, f[1] + pre[n] - pre[1]);
	mx.push (1); mn.push (1); minpos = 1; mxv = mnv = a[1];
	for (int i = 2; i <= n; ++i) {
		tmp1 = i; mxv = max (mxv, a[i]); mnv = min (mnv, a[i]);
		while (mx.size ()) {
			update_incre (1, mx.top (), tmp1 - 1, a[i] - a[tmp1]);
			if (mx.size () > 1 && a[i] >= a[mx.top ()]) {
				tmp1 = mx.top ();
				mx.pop ();
			} else break;
		}
		mx.push (i); tmp2 = i;
		while (mn.size ()) {
			update_incre (1, mn.top (), tmp2 - 1, a[tmp2] - a[i]);
			if (mn.size () > 1 && a[i] <= a[mn.top ()]) {
				tmp2 = mn.top ();
				mn.pop ();
			} else break;
		}
		mn.push (i);
		while (pre[i] - pre[minpos] > W)
			++minpos;
		f[i] = query (1, minpos, i - 1);
		if (pre[i] <= W) f[i] = min (f[i], pre[n] + mxv - mnv);
		update_sing (1, i, f[i] + pre[n] - pre[i]);
	}
	printf ("%lld", f[n]);

	return 0;
}