最近刷到一道三段最大子段和的问题，发现自己连一段最大子段和都写不出来。于是怒刷四道题，特此记录……
一 单段最大子段和问题
来源
给出一段长为$N$的序列$s$，选出其中连续且非空的一段使得这段和最大。$N⩽200000$
设$f_i$为以$i$结尾（$i$必须要选）时的最大子段和大小。则有$f_i = \max f_{i-1}+s_i, s_i$，也就是与前面的合并成一段或者新开另一段。
最后一个元素不一定要选，那么答案就是$\max\limits_{i=1}^n f_i$。
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 2e5+5;
int n,f[CN],g[CN];
int main()
{
memset(g,-0x3f,sizeof(g));
f[0] = -0x3f3f3f3f3f;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int s; scanf("%d",&s);
f[i] = max(f[i-1]+s,s);
g[i] = max(g[i-1], f[i]);
}
printf("%d",g[n]);
return 0;
}
|
二 多段最大子段和问题
给定一个长为$n$的数列$s$，从中找到$m$个无交集的连续子数列使其和最大。
有一个很优秀的DP状态设计：
设$f_{i,j,0/1}$表示考虑前$ i $个位置，划分$ j $段，且第$ i $个位置的数 选(最后一维为$1$) 或 不选(最后一维为$0$) 时，得到的答案。
初始状态总是$f_{1,0,0} = 0,f_{1,1,1} = s_1$，其余$f$值全清成$-\infty$。
时空复杂度都是$O(nm)$，在$m$比较小时适用。
实际上还有一种能应对$n,m$都很大的情况的贪心通解，典型题是BZOJ2288（貌似已经找不到了）。但是我太菜，理解不了，请参阅hzwer神犇的题解。
1 两段最大不相邻子段和
来源
给定一个长度为$n$的整数序列$s$，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出最大和。一个连续子序列的和为该子序列中所有数之和。每个连续子序列的最小长度为1，并且两个连续子序列之间至少间隔一个数。
转移方程是$f_{i,j,0} = \max\begin{Bmatrix} f_{i-1,j,0},f_{i-1,j,1} \end{Bmatrix}, f_{i,j,1} = \max \begin{Bmatrix} f_{i-1,j,1}+s_i, f_{i-1,j-1,0}+s_i \end{Bmatrix}$。后面的方程必须满足$j>0$才可以转移，因为状态$f_{i,0,1}$没有意义。
第一个方程不用解释，第二个的意思是和前面的一块组成$j$个或者自己组成第$j$个。因为两个子段不能相邻，故后面的那个不能从$f_{i-1,j-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
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define LL long long
const int CN = 1e6+6;
const LL INF = 0x7f7f7f7f7f7f7f7f;
LL read(){}
int n;
LL f[CN][3][2],s[CN];
int main()
{
n = read();
for(int i=1;i<=n;i++) s[i] = read();
memset(f,-0x7f,sizeof(f));
f[1][0][0] = 0; f[1][1][1] = s[1];
for(int i=2;i<=n;i++){
for(int j=0;j<=2;j++){
f[i][j][0] = max(f[i-1][j][1], f[i-1][j][0]);
if(j > 0) f[i][j][1] = max(f[i-1][j][1]+s[i], f[i-1][j-1][0]+s[i]);
}
}
printf("%lld",max(f[n][2][0], f[n][2][1]));
return 0;
}
|
2 三段最大子段和
来源 （实际上是从hzwer神犇的博客上搞来的套题，一部分题目放在了这个题组里。）
给定一个长为$n$的数列$s$，从中找到三个无交集的连续子数列使其和最大。
转移方程是$f_{i,j,0} = \max\begin{Bmatrix} f_{i-1,j,0},f_{i-1,j,1} \end{Bmatrix}, f_{i,j,1} = \max \begin{Bmatrix} f_{i-1,j,1}+s_i,f_{i-1,j-1,1}, f_{i-1,j-1,0}+s_i \end{Bmatrix}$。同样，后面的方程必须满足$j>0$才可以转移，因为状态$f_{i,0,1}$没有意义。
第二个方程的意思是：和前面的一块组成$j$个，或者从$i-1\to i$这个位置断成两个数列，或者自己组成第$j$个。
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define LL long long
const int CN = 1e6+6;
const LL INF = 0x7f7f7f7f7f7f7f7f;
LL read(){}
int n;
LL f[CN][4][2],s[CN];
int main()
{
n = read();
for(int i=1;i<=n;i++) s[i] = read();
memset(f,-0x7f,sizeof(f));
f[1][0][0] = 0; f[1][1][1] = s[1];
for(int i=2;i<=n;i++){
for(int j=0;j<=3;j++){
f[i][j][0] = max(f[i-1][j][1], f[i-1][j][0]);
if(j > 0) f[i][j][1] = max(f[i-1][j][1],
max(f[i-1][j-1][0], f[i-1][j-1][1])) + s[i];
}
}
printf("%lld",max(f[n][3][0], f[n][3][1]));
return 0;
}
|
三 环形双段最大子段和问题
来源
给出一段长为$n$的环状序列$s$，即认为 $s_1$ 和 $s_n$ 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。
实际上就是两种情况：选两段最大子段和（类似于这样：xxx√√xx√√√x）或选三段首尾都需要选的最大子段和（类似于这样：√√√xx√√xxx√）。
第一种情况直接跑两段最大子段和就好了，第二种情况可以看成区间总和减掉一个两段最小不相邻子段和，并且这两段中不能包括$s_1$和$s_n$。其实改一改DP边界就解决了。
代码：
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define LL long long
const int CN = 1e6+6;
const LL INF = 0x7f7f7f7f7f7f7f7f;
LL read(){}
int n;
LL f[CN][3][2],s[CN],ans = -INF,sigma = 0;
int main()
{
n = read();
for(int i=1;i<=n;i++)
s[i] = read(),sigma += s[i];
memset(f,-0x7f,sizeof(f));
f[1][0][0] = 0; f[1][1][1] = s[1];
for(int i=2;i<=n;i++){
for(int j=0;j<=2;j++){
f[i][j][0] = max(f[i-1][j][1], f[i-1][j][0]);
if(j > 0) f[i][j][1] = max(f[i-1][j][1],
max(f[i-1][j-1][1], f[i-1][j-1][0])) + s[i];
}
}
ans = max(ans, max(f[n][2][0], f[n][2][1]));
memset(f,0x7f,sizeof(f));
f[2][0][0] = 0; f[2][1][1] = s[2];
for(int i=3;i<n;i++){
for(int j=0;j<=2;j++){
f[i][j][0] = min(f[i-1][j][1], f[i-1][j][0]);
if(j > 0) f[i][j][1] = min(f[i-1][j][1],f[i-1][j-1][0]) + s[i];
}
}
ans = max(ans, sigma-min(f[n-1][2][0], f[n-1][2][1]));
printf("%lld",ans);
return 0;
}
|
