是的，又是一道考试时想出正解没有打出来的题目
根据题意，我们很容易想到一个朴素的类区间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$。
#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;
}
发表回复