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

题目大意：

给予n和x，然后是一个大小为n的数组。
F(k)表示当你将数组中任意k个数加上x之后的最大子段和，要求输出F(0),F(1),…,F(n)。
n的范围是5000以内。

解：

范围是5000以内，说明可以接受O（n2）的复杂度，一个数组能够接受这样的复杂度说明什么？
说明可以求出任意一个子段的子段和。
此题到此结束。
首先求前缀和，然后处理出长度为i的最大子段和。
对于k，讨论子段长度为0-n的情况
当该子段长度小于k，则加上子段长度x，否则加上kx，取结果最大的那个子段。
与其说是dp不如说是前缀和的应用吧。
所以说，当子段问题能够接受O（n2）的时候，就别d什么p了，直接暴力吧。

代码

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

#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 1000005
#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);
#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[5005],dp[5005][5005],mx[5005],qzh[5005];
int main() {
	cfast;
	int t;
	cin >> t;
	while (t--) {
		int n, x;
		cin >> n >> x;
		inc(i, 1, n + 1) {
			cin >> a[i];
			qzh[i] = qzh[i - 1] + a[i];
		}
		mx[0] = 0;
		inc(i, 1, n + 1) {
			mx[i] = -1e9;
			inc(j, 1, n + 2 - i) {
				mx[i] = max(mx[i], qzh[j + i-1] - qzh[j - 1]);
			}
		}
		inc(k, 0, n + 1) {
			ll ans = -1e9;
			inc(j, 0, n + 1) {
				if (j <= k)ans = max(ans, mx[j] + j * x);
				else ans = max(ans, mx[j] + k * x);

			}
			cout << ans << " ";
		}
		cout << endl;
	}
}
/*
3
4 12 6 
*/