plafle's blog

plafle's blog

the pursuit of rationalism

发表于 更新于

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

发表于 更新于

​ 希望能够幸福地做人，合理地度日，内心安定平和，即使身处逆境也始终保持追求。同时也希望能够通过文字与各位交流这方面的经验，于苦难中彼此慰藉。

发表于 更新于

机器学习笔记

1. 安装Pytorch

​ 在这里选择你的选项，然后在命令行中打pytorch官网提供的命令，打完之后如果遇到了错误，那么考虑是不是你的python版本过高。访问Start Locally | PyTorch这里来确认pytorch是否支持你的python版本。

​

2. 《动手学深度学习》笔记

2.1 数据操作

  • 注意：两个张量如果可以广播，那么：

    • 每个张量至少有一个维度。
    • 迭代维度尺寸时，从尾部的维度开始，维度尺寸 ​ 或者相等， ​ 或者其中一个张量的维度尺寸为 1 ， ​ 或者其中一个张量不存在这个维度

    例如：

    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
    import torch

    # 示例1：相同形状的张量总是可广播的，因为总能满足以上规则。
    x = torch.empty(5, 7, 3)
    y = torch.empty(5, 7, 3)


    # 示例2：不可广播（ a 不满足第一条规则）。
    a = torch.empty((0,))
    b = torch.empty(2, 2)


    # 示例3：m 和 n 可广播：
    m = torch.empty(5, 3, 4, 1)
    n = torch.empty(   3, 1, 1)
    # 倒数第一个维度：两者的尺寸均为1
    # 倒数第二个维度：n尺寸为1
    # 倒数第三个维度：两者尺寸相同
    # 倒数第四个维度：n该维度不存在


    # 示例4：不可广播，因为倒数第三个维度：2 != 3
    p = torch.empty(5, 2, 4, 1)
    q = torch.empty(   3, 1, 1)

    # 示例5：a 和 b 可广播：
    m = torch.arange(12).reshape(2,2,3)
    n = torch.tensor(1)
2.4 微积分
  • 2.4.3的梯度没有懂，尤其是涉及矩阵的部分
2.5 自动微分

  • 2.5.1 一个标量函数如何对一个向量求导？

    标量 y 对 n 维列向量 \(x = (x_1,x_2,...,x_n)^T\)求导，其结果还是一个n维列向量，结果是\((\frac {\partial y} {\partial x_1}, \frac {\partial y} {\partial x_2} ... \frac {\partial y} {\partial x_n})^T\)

    标量 y 对 n 维行向量 \(x = (x_1,x_2,...,x_n)\)求导，其结果还是一个n维行向量，结果是\((\frac {\partial y} {\partial x_1}, \frac {\partial y} {\partial x_2} ... \frac {\partial y} {\partial x_n})\)

0%