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

题目大意：

CF1699D Almost Triple Deletion

笑死，平时在那边叫怎么没有DP做，真正有DP的时候么又不会了，普信男真的是。

题目大意：一个数组（n<=5000），可以进行任意次操作：删除两个相邻的数值不同的数（删除后自动合并），使得最后得到一个只包含一种数值的数的数组，求这个数组的最大长度。

解：

题解：通过观察其实可以发现：当一个长度为偶数的数组中出现频率最高的数频率小于数组长度的一半时，你永远可以去删掉这个数组。
由于支持n2复杂度，我们可以求出对于任意两个下标i,j，是否可以删除ij这整个区间上的数。
这样的删除导致的一个结果就是i-1和j+1的数合并了起来，显然我们只希望a[i-1]==a[j+1]的时候进行这样的合并，于是对于每个j，去遍历有哪些i可以删除，然后进行转移就可以了。
值得一提的是，最后的数组还要满足一个条件——如果数组结尾是j，那么[j+1,n]这个区间可以被删除。
还有一些细节上的问题，比如当a[i]=a[i-1]时的状态转移，如果a[i]=0而且i并不是开头之前的数（为了方便转移，在数组前面加了个数）时是无法进行转移的。

2300分的题感觉实际上算法含量并没有想象的那么高，还是以思维为主，量变产生质变，继续加油吧。
好热，没有干劲了捏。

代码

代码
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#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;
#define endl '\n'
#define PI 3.14159265358979
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll getpos(int p, ll n) {
	return n / cpow(10, p - 1) % 10;
}
ll getwei(ll n) {
	int res = 0;
	while (n) {
		res++;
		n /= 10;
	}
	return res;
}
/*

---------------------------------------------------------------------

*/

int a[5005],dp[5005][5005];
int cnt[5005];
vector<int> canto[5005];
int main() {
	cfast;
	int t = 1;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		inc(i, 1, n + 1) {
			canto[i].clear();
			cin >> a[i];
		}
		inc(i, 1, n + 1) {
			inc(j, 1, n + 1) {
				cnt[j] = 0;
			}
			int mx = 0;
			inc(j, i, n + 1) {
				cnt[a[j]]++;
				mx = max(mx, cnt[a[j]]);
				if (mx <= (j - i + 1) / 2&&(j-i+1)%2==0) {
					canto[j].push_back(i);
				}
			}
			
		}
	
		inc(i, 1, n + 1) {
			/*cout << "canto." << i << " : " << endl;
			inc(j, 0, canto[i].size()) {
				cout << canto[i][j] << " ";
			}cout << endl;*/
			inc(j, 0, n + 1) {
				dp[i][j] = 0;
			}
		}
		inc(i, 1, n + 1) {
			int mx = 0;
			if (a[i] == a[i - 1]||i==1) {
				if(dp[a[i]][i-1]==0&&i!=1){}
				else {
					mx = dp[a[i]][i - 1] + 1;
					dp[a[i]][i] = dp[a[i]][i - 1] + 1;
				}
			}
			inc(j, 0, canto[i-1].size()) {
				int to = canto[i-1][j]-1;
				if (to == 0 || a[to] == a[i]) {
					if (dp[a[i]][to] == 0 && to != 0)continue;
					mx = max(mx, dp[a[i]][to] + 1);
				}
			}
			dp[a[i]][i] = mx;
			//cout << "dp." << a[i] << "." << i << " = " << dp[a[i]][i] << endl;
		}
		int ans = dp[a[n]][n];
		inc(j, 0, canto[n].size()) {
			int to = canto[n][j] - 1;
			inc(i, 1, n + 1) {
				ans = max(ans, dp[a[i]][to]);
			}
		}
		cout << ans << endl;
	}
}
/*
1
25
1 1 2 1 3 3 2 3 2 3 3 1 2 4 2 3 2 2 1 2 3 4 1 2 3
*/