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

题目大意：

CF 1475G Strange Beauty
题目大意：给一个长度为n的数组（n级别为2e5），数字范围为2e5，求其中最长的beautiful子序列，定义为其中任意一对数中较大的都能整除较小的。

解：

很容易看出，我们要求的目标beautiful子序列是一个前一项必为后一项因数的子序列，由于数字范围为2e5，实际上我们可以预处理求出每个数字的所有因数（复杂度为O(1+1/2+…+1/n）。
问题已经解决了，从最大的数开始遍历其所有因数，只要原数组里有就打上标记，并且求这个找到的数能找到的因数数量叠加上去，返回一个找到的数最多的路线，理论上复杂度是O(n)，嗯理论上。
已经标记过的数就不用再找了。
值得一提的是这题由于常数较大，如果优化不当dfs做法会超时，所以其实也可以选择顺序遍历的dp做法（虽然复杂度都是O(1+1/2+…+1/n)，但是真的快了很多，原本5秒都t了的dfs顺序dp只花了919ms），所以说，能用dp一次性解决的就不要用记忆化dfs了，血的教训，实际上dp的代码也简洁很多耶。
Dp的转移方程和for gamers. By gamers.类似。

代码

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

#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],vis[10][maxn],cnt[10][maxn],dp[10][maxn];

int main()
{
	cfast;
	int t;
	scanf("%d", &t);
	for(int tt=0;tt<t;tt++){
		memset(dp, 0, sizeof(dp));
		int n;
		scanf("%d", &n);
		inc(i, 0, n) {
			scanf("%lld", &a[i]);
			cnt[tt][a[i]]++;
		}
		sort(a, a + n);
		ll mx = 0;
		inc(i, 0, n) {
			if (i > 0 && a[i] == a[i - 1])continue;
			for (int j = a[i]; j <= 200000; j += a[i]) {
				if (j == a[i])dp[tt][j] = max(dp[tt][j], cnt[tt][j]);
				else dp[tt][j] = max(dp[tt][j], cnt[tt][j] + dp[tt][a[i]]);
				mx = max(mx, dp[tt][j]);
			}
		}
		printf("%lld\n", n - mx);
		
	}
}
/*
3
4 12 6 
*/