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

题目大意：

CF1616D Keep the Average High

题目大意：给一个数组和一个x，大小范围为5e4，数字范围为±1e6，你可以为其中任意个数上标记，要求最终对于每个长度大于1的子段来说，要么其中有数没有被标记，要么其平均值>=x，问最多能打多少个标记。

解：

实际上标记起的作用在于把原来的数组划分为k段，并且保证每段内包括自身的所有子段平均值都大于等于x，那么显然这个标记我是能打就打，不能打就算了，因为不标记的这个数依然会参与之后的计算，所以不存在我可以选择不打这个标记反而导致之后可以多打标记的情况（为什么，好好想想是不是这样）。
好接下来，对于平均值大于等于x的说法实在太麻烦了，因此我们简化一下吧，把所有数都减去x，只要让段和大于等于0就相当于平均值大于等于x。
然后如何保证每段中的所有子段和都大于等于0呢？
如果我当前的段已经能够保证合格，现在我给这个段新添加一个数，那么最有可能<0的段显然肯定是后缀和最小的那个段，但是我不可能一个一个去遍历后缀和吧，复杂度不允许呀。
注意，我原本后缀和最小的那个段即使在加上新的数之后，它本身还依然是后缀和最小的那个段，因此对于我新加了一个数之后新得到的段中后缀和最小的段就是原本后缀和就最小的段。不，还有可能是他本身，因为他本身在上一次计算中无法单独存在（段长度>1），但是在下一次计算的时候就可能是他单独加上新的数了。用dp[i]表示从当前开始处（设为tmp）到i的最小后缀和，dp[i]=min(dp[i-1]+a[i],a[i])，添加新的数的时候，判断dp[i-1]+a[i]是否大于等于0，如果不是，那么这个数没法打标记了，如果用cnt记录下无法打标记的数的数量，那就是使cnt++，接下来再让tmp从下一个数开始。
这是道偏向思维的线性dp，dp含量其实不高，重要的是找到转化原题目的方法，dp只是手段而不是方法，不要看到题目看着像或者标签有dp就直接开始硬想状态方程。Dp从来都是把思维题想着想着，转化着就发现，草，这不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

#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);
using namespace std;
ll a[50001];
int dp[50001];
int main()
{
	cfast;
	int t;
	cin >> t;
	while (t--) {
		int n;
		ll x;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cin >> x;
		int num = 0;
		int tmp = 0;
		for (int i = 0; i < n; i++) {
			a[i] -= x;
			if (tmp == i) {
				dp[i] = a[i];
			}
			else {
				if (a[i] + dp[i - 1] < 0) {
					tmp = i + 1;
					num++;
					continue;
				}
				else {
					dp[i] = min(a[i] + dp[i - 1], a[i]);
				}
			}
		}
		cout <<n-num << endl;
	}

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