把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

给N个数，求m个不相交子段的最大段和，每个子段大小不限。

解：

熟悉线性DP的人很快就会发现，这其实就和普通的最大子段和没什么区别。
普通子段和的状态转移为：对于a[i]，选择将其加入其之前的子段或不加入。
多段子段和则是：对于a[i]，选择将其加入上一个序号为j的子段或是自己作为第j个子段段头，注意是上一个，因此在空间不够的时候可以直接上滚动数组。
DP[i][j]表示共有j段，结尾为i时的最大子段和，写法上有些细节，但是都没什么影响，唯一有影响的是在遍历第j个子段的子段头时要从第j个数开始。
如果一定要有m段（也就是每段长度都大于0）的话取DP[n][m]，否则要取max(DP[n][k])。
久违地放个代码，只是因为还存着而已，才不是为了你写的呢。

代码

代码
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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll a[maxn];
ll bdp[2][maxn],dp[2][maxn];
int main()
{
	cfast;
	int t;
	cin >> t;
	while (t--) {
		memset(bdp, 0, sizeof(bdp));
		int m, n;
		cin >> m >> n;
		for (int i = 1; i <= n; i++)cin >> a[i];
		ll ans = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = i; j <= n; j++) {
				dp[1][j] = max(dp[1][j - 1] + a[j], bdp[0][j - 1]+a[j]);
				bdp[1][j] = max(bdp[1][j - 1], dp[1][j]);
			//	cout << dp[1][j] << " ";
			}
			//cout << endl;
			ans = max(ans, bdp[1][n]);
			for (int j = 1; j <= n; j++) {
				dp[0][j] = dp[1][j];
				bdp[0][j] = bdp[1][j];
			}
		}
		cout << ans << endl;

	}


}
/*
2
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
*/