Acwing299题解

发表于 更新于

Acwing 299 裁剪序列（也许它能帮到你）

1.题意：

给定一个长度为 \(N\) \((N \le 1e5)\)的序列 \(A\) ，要求把该序列分成若干段，在满足“每段中所有数的和”不超过M的前提下，让“每段中所有数的最大值”之和最小。

试计算这个最小值。

2.分析

朴素DP：

  • 状态：设\(f[i]\) 表示将前 \(i\) 个数分为若干段，每段和不超过 \(m\) 时，最大值之和的最小值。

  • 转移方程： \[ f[i] = min(f[j] + max(a[j + 1],a[j + 2],……a[i])) \ \ \ \ (\sum_{k = j + 1}^na_k \le m) \] 其中的区间最大值和区间和分别可以用ST表和前缀和完成。

    复杂度\(O(n^2)\).

    接下来来考虑优化。

若\(j\)可能作为\(f[i]\)的唯一最优决策，那么\(j\)必须满足下面两个条件之一：

  • \(a[j]\)是\(a[j],a[j + 1],……,a[i]\)中的最大值
  • \(\sum_{k = j}^i a_k > m\)

证明：

若\(j\)对上述两个条件都不满足，那么对于决策\(j - 1\)：

因为\(\sum_{k = j}^i a_k \le m\)，所以决策\(j - 1\)是合法的。

同时因为\(a[j]\)不是\(a[j],a[j + 1],……,a[i]\)中的最大值，所以

\[ \max(a[j + 1],a[j + 2],……a[i]) = \max(a[j],a[j + 1],a[j + 2],……a[i]) \]

又因为\(f[i]\)单调不减，所以： \[ f[j - 1] + max(a[j],a[j + 1],a[j + 2],……a[i])\le f[j] + max(a[j + 1],a[j + 2],……a[i]) \] 即决策\(j - 1\)比决策\(j\)更优或相等，所以决策\(j\)不会是唯一的最优决策。

对于考虑满足第二个条件的决策，我们可以预处理出\(c[i]\)，表示满足\(\sum_{k = j}^ia_k \le m\)的最小的\(j\)。然后对于\(f[i]\)，执行f[i] = min(f[i],f[c[i] - 1]+max(a[c[i]],a[c[i] + 1],a[c[i] + 2],……,a[i]))

​

对于考虑满足第一个条件的决策，我们可以考虑用单调队列来优化DP。

循环变量\(i\)，循环开始先从队头剔除不合法的决策（即状态转移中的条件）

然后将\(i\)入队，同时维护单调队列元素\(x\)的\(a[x]\)单调不增，保证单调队列中的决策都是可能的最优决策。

但是这样我们还是需要循环整个单调队列枚举所有决策。

接下来我们来集中解决这个问题。

我们先建立一个used数组。

我们再建立一个小根堆，其中的元素为(id,x)，按x作为比较的依据。表示对于决策\(id\)，x表示\(f[id] + max(a[id + 1],a[id + 2],……a[id])\)。

每次向单调队列中插入一个新决策\(j\)时，同时也向堆中插入这个决策\((j,f[j] + max(a[j + 1],a[j + 2],……,a[i]))\)。当从单调队列中删除一个决策\(j\)时，令\(used[j] = 1\)。以后从堆顶取数时，需要判断\(used[top().id]\)是否为1，若是1，需要将其弹出，重新取堆顶。

我们能这样做的一个原因在于一旦决策\(j\)被丢弃，以后该决策就不可能再次出现在单调队列中了。

现在我们还需要一个问题要解决：当\(i\)变成\(i + 1\)时，有可能 \[ \max(a[j + 1],a[j + 2],……,a[i]) \neq \max(a[j + 1],a[j + 2],……,a[i],a[i + 1]) \] 即对于每个\(i\)，我们都需要将堆中的元素重新更新一遍。

为了方便起见，我们称呼\(max(a[j + 1],a[j + 2],……,a[i])\)为决策\(j\)对于\(i\)的“决策 值，简写为\(p(j,i)\)。

我们观察一下何时\(p(j,i) \neq p(j,i + 1)\).发现：将\(i\)入队后，在单调队列\(\{q_1,q_2,……,q_s,i\}\)中，因为\(a[q_1] \ge a[q_2] \ge …… a[i]\)，所以对于决策\(q_1,q_2,……,q_{s - 1}\)，\(p(q_1,i) = p(q_1,i + 1)\),\(p(q_2,i) = p(q_2,i + 1)\),……,\(p(q_{s - 1},i) = p(q_{s - 1},i + 1)\),只有\(p(q_s,i)\)可能不等于\(p(q_s,i + 1)\).

所以\(i\)入队后，我们再将决策\((id = q_s,x = f[q_s]\) + $ max(a[q_s + 1],a[q_s + 2] ，……，a[i]))\(重新入队，作为修正。可以发现，\)max(a[q_s + 1],a[q_s + 2] ，…，a[i]) = a[i]$。

但是，决策\(q_s\)在堆里面原来的错误的值并没有被修改。为了解决这个问题，我们可以给堆的结构体中加一个变量\(y\)表示当前决策目前的"决策值"。取出堆顶的时候，如果发现堆顶决策的”决策值“不等于堆顶决策对于\(i\)应有的决策值时，就将该决策视为无效，重新取堆顶。

Code:

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
#include<iostream>
#include<cstdio>
#include<cstring> 
#include<queue>

#define int long long
using namespace std;

const int maxn = 1e5 + 5,inf = 1e15;

struct node {
	int id,x,y;
	friend bool operator < (node a,node b) {
		return a.x + a.y > b.x + b.y;
	}	
};


int q[maxn << 3],t,w;

int a[maxn],n,m,sum[maxn],lg[maxn],st[maxn][30],c[maxn];
int f[maxn]; //f[i] 表示将前 i 个数分为若干段，每段和不超过 m 时，最大值之和的最小值。 
bool used[maxn];

priority_queue<node> h;

int query(int l,int r) {
	int len = lg[r - l + 1];
	return max(st[l][len],st[r - (1 << len) + 1][len]); 	
}

signed main() {
	scanf("%lld %lld",&n,&m);
	for (int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		if (a[i] > m) {
			puts("-1");
			return 0; 
		}
		sum[i] = sum[i - 1] + a[i];
		st[i][0] = a[i];
	}
	lg[0] = -1;
	for (int i=1; i<=n; i++)
		lg[i] = lg[i >> 1] + 1;
	
	for (int i=1; i<=lg[n]; i++)
		for (int j=1; j<=(n - (1 << i) + 1); j++)
			st[j][i] = max(st[j][i - 1],st[j + (1 << (i - 1))][i - 1]);
			
	c[0] = 1;
	for (int i=1; i<=n; i++)
		for (int j=c[i - 1]; j<=n; j++)
			if (sum[i] - sum[j - 1] <= m) {
				c[i] = j;
				break;
			}
	
	// c[i] 表示 a[j] + a[j] + ……+ a[i] <= m的最小的j。
	// f[i] 表示将前 i 个数分为若干段，每段和不超过 m 时，最大值之和的最小值。 
	t = 1,w = 0;
	
	for (int i=1; i<=n; i++) {
		f[i] = inf;
		f[i] = min(f[i],f[c[i] - 1] + query(c[i],i)); //考虑条件2
		while (t <= w && sum[i] - sum[q[t]] > m) {
			used[q[t]] = 1;
			t++;
		} //从队头弹出非法决策
			
		while (t <= w && a[q[w]] < a[i]) {
			used[q[w]] = 1;
			w--;
		} //从队尾弹出不必要决策
		q[++w] = i;
		
		if (t < w) 
			h.push((node){q[w - 1],f[q[w - 1]],a[i]}); //修正“决策值”
		
		while (!h.empty() && (used[h.top().id] || h.top().y < query(h.top().id + 1,i)))
			h.pop();
		
		if (!h.empty())
			f[i] = min(f[i],h.top().x + h.top().y); 
	
	}
	printf("%lld\n",f[n]);
	return 0;
}