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

题目大意：

CF 846C Four Segments
题目大意，给一个长度为n（级别为5000）的数组，要求将其划分为4段，第一、三段里的数加，第二、四段的数减，求如何划分使得结果最大。

解：

如果是直接暴力那么复杂度是O(n3)，但是如果只是分成两段的复杂度不就变成了O(n)么，于是能不能把这个问题改为三次分成两段呢？由于还要多一个选段的右端点的过程，所以复杂度是O(3*n2)，能过，记录答案时要注意区间的开闭问题，还是有一定细节在里面的。
与其说这题是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
68
69
70
71
72
73
74
75
76
77

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
#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);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
using namespace std;
ll a[maxn],dp[5][maxn],qzh[maxn],rcd[5][maxn];
int main()
{
	cfast;
	int n;
	cin >> n;
	inc(i, 1, n + 1)cin >> a[i];
	inc(i, 1, n + 1)qzh[i] = qzh[i - 1] + a[i];
	dp[0][0] = 0;
	inc(x, 1, 5) {
		inc(i, 1, n + 1) {
			if (x == 1) {
				dp[x][i] = qzh[i];
				rcd[x][i] = 1;
				continue;
			}
			if (x % 2 == 1)
				dp[x][i] = qzh[i];
			else
				dp[x][i] = -qzh[i];
			rcd[x][i] = 1;
			inc(j, 0, i+1) {
				ll qj = qzh[i] - qzh[j];
				if (x % 2 == 1) {
					if (dp[x - 1][j] + qj>=dp[x][i]) {
						dp[x][i] =dp[x - 1][j] + qj;
						rcd[x][i] = j+1;
					}	
				}
				else {
					if (dp[x - 1][j] - qj >= dp[x][i]) {
						dp[x][i] = dp[x - 1][j] - qj;
						rcd[x][i] = j+1;
					}
				}
			}
			//cout << "rcd."<<x<<"."<<i<<" = "<<rcd[x][i] <<", dp= "<<dp[x][i]<< endl;
		}
	}
	int ans[3];
	int tmp = n;
	inc(i, 0, 3) {
		ans[2 - i] = rcd[4-i][tmp]-1;
		tmp = rcd[4-i][tmp]-1;
	}
	inc(i, 0, 3) {
		cout << ans[i] << " ";
	}
}
/*
3
4 12 6 
*/