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;
}