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

题目大意：

CF 1637D
Yet Another Minimization Problem
说实话感觉这题我的做法并不是正解，但是简单无脑。
题目大意为给定两个长度为n的数组，（n范围为100，数字范围也为100），你可以将他们俩对应位置的数进行交换，交换次数任意，求两个数组分别的数组内两两相加的和的平方和的和的最小值(有点绕)，小列个式子可以发现问题可以转化为将a数组-b数组得到c数组，在c数组的每个数前面标加减号来使得结果的绝对值最小。

解：

由于数字范围为100，n也为100，实际上c数组的和最大为10000，最小为-10000，如果用线性dp的话数组为100*20000也就是1e6，完全符合要求，dp[i][j]表示进行到第i个数且和为j的情况，对于一个新的i，状态转移为dp[0][0]=1，dp[i][j+ci]=dp[i-1][j]和dp[i][j-ci]=dp[i-1][j]，最后只要判断dp[i][n]=1中n绝对值最小的那个即可。
同时对于每一个值记录它对应的是加还是减，求结果的时候还需要用到。
为了偷懒不用map，写法看起来有点缺乏观赏性……
像这种n等于100且每个n都有两种或多种选择的时候，状压是不可取的，毕竟是2^100嘛，可以注意到最后我们把这个接近2^100的可能性限定在了20000内，这真的是因为数组中数字大小绝对值在100以内吗？真的不是因为一共只有100个数吗，如果a[i]<=1e9的时候难道就不行了吗？
如果是去离散化，将每步得到的答案用set这种东西储存起来，然后dp……
如果a1=1,a2=2,a3=4,…,a100=2^101还是寄，目前想不到解法。

好，Yet Another Minimization Problem 2
给定n(1<=n<=100)，一个数组cn，现在可以进行任意次操作，选定i使得c[i]=-c[i]，现在要使任意次操作后得到的c数组之和绝对值最小，求该绝对值大小。

……挺无语的就
代码(当然不是问题2)：

代码

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
using namespace std;
int a[101],b[101],c[101];
int dp[20001][101], track[20001][101];
int v[20001][101];
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		memset(v, 0, sizeof(v));
		int n;
		cin >> n;
		ll ans = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> b[i];
			c[i] = a[i] - b[i];
		}
		int fina = 0, mi = 1e9;
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				dp[10000 + c[i]][0] = c[i];
				track[10000+c[i]][0] = 1;
				dp[10000 - c[i]][0] = -c[i];
				track[10000 - c[i]][0] = 0;
				v[10000 + c[i]][0] = 1;
				v[10000 - c[i]][0] = 1;
			}
			else {
				for (int j = 0; j <= 20000; j++) {
					if (v[j][i - 1] == 0)continue;
					dp[j + c[i]][i] = j-10000 + c[i];
					track[j + c[i]][i] = 1;
					dp[j - c[i]][i] = j-10000 - c[i];
					track[j - c[i]][i] = 0;
					v[j + c[i]][i] = 1;
					v[j - c[i]][i] = 1;
					if (i == n - 1) {
						int d1 = dp[j + c[i]][i];
						if (d1 < 0)d1 = -d1;
						int d2 = dp[j - c[i]][i];
						if (d2 < 0)d2 = -d2;
						if (d1 < mi) {
							fina = j + c[i];
							mi = d1;
						}
						if (d2 < mi) {
							fina = j - c[i];
							mi = d2;
						}
					}
				}
			}
		}

		for (int i = n - 1; i >=0; i--) {
			//cout << "when " << i << " final=" << fina-10000 << endl;
			if (track[fina][i] == 0) {
				int tmp = a[i];
				a[i] = b[i];
				b[i] = tmp;
				fina += c[i];
				//cout << "reversed" << i << endl;
			}
			else fina -= c[i];
		}
		for (int i = 0; i < n; i++) {
			ans += a[i] * a[i] * (n - 1);
			ans += b[i] * b[i] * (n - 1);
			for (int j = 0; j < i; j++) {
				ans += 2*a[i] * a[j];
				ans += 2*b[i] * b[j];
			}
		}
		cout << ans << endl;
	}
}