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

题目大意：

CF 1579G Minimal Coverage

题目大意：给n个数（n级别为1e4）的数组a（a[i]级别为1e3），你一开始在原点，你可以选择向左或者右走a[i]步，求最后你走过的路的最小覆盖长度。

解：

一开始以为是类似于快递员问题，但是这个问题的选择非常固定，而且对于每个线段，你的结束位置并不一定在端点上，而且这个结束位置和下一步的状态有关。这里我已经说“状态”了，因为很显然这题就是dp，一眼就能看出来。
仔细想想，对于每个状态来讲，当前他处在的位置并不重要，重要的只是他左边最远去过的距离和右边最远去过的距离，而这两个距离的和就是我们要求的答案，所以实际上我们的状态中只要包含其中的一个距离就行。
dp[i][j]表示在第i个数的时候我离向左边去过的最远的点的距离为j时向右边达到的最远距离，那么我状态转移就显而易见了，有四种情况，自己画图去。
关键在于这么dp我要遍历多久捏，我可以一路跑到最远的地方，离左边距离为1e4*1e3。
实际上大家可以模拟一下就会发现，最终的结果最大也不会超过两倍的最大线段的长度（因为实在不行我可以在无视最大的那个线段的情况下，能向中间就向中间），所以需要遍历的j只有2000个（然后我怂了，写了3000个，还用vector存，丢人）

这题其实比较接近几何的领域吧，面对这种不是很明显的状态转移，千万不要去想复杂的数学化简方法，一步到位的状态转移永远是最好的，状态直接定为好算的那个就行了。
有时候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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#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 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 dp[3000],roller[3000],vis[3000];
ll a[10005];
vector<int> hav[10005];
int main(){
	cfast;
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		inc(i, 1, n + 1)scanf("%d", &a[i]);
		hav[1].push_back(0);
		clr(dp, 3000);
		dp[0] = 0;
		ll ans = 1e5;
		inc(i, 1, n + 1) {
			//cout << "i = " << i << endl;
			vset(roller, 3000, 1e5);
			clr(vis, 3000);
			inc(j, 0, hav[i].size()) {
				int tj = hav[i][j];
				if (tj >= a[i]) {

					roller[tj - a[i]] = min(roller[tj - a[i]], dp[tj] + a[i]);
					if (i == n)ans = min(ans, tj-a[i]+roller[tj - a[i]]);
					if (vis[tj - a[i]] == 0)hav[i+1].push_back(tj - a[i]),vis[tj-a[i]]=1;
					//cout << "r." << tj - a[i] << " = " << roller[tj - a[i]] << endl;
					if (tj + a[i] <= 2000) {
						roller[tj + a[i]] = min(roller[tj + a[i]], max((ll)0, dp[tj] - a[i]));
						if (i == n)ans = min(ans, tj + a[i] + roller[tj + a[i]]);
						if (vis[tj + a[i]] == 0)hav[i + 1].push_back(tj + a[i]), vis[tj + a[i]] = 1;
						//cout << "r." << tj + a[i] << " = " << roller[tj + a[i]] << endl;
					}
				}
				else {
					roller[0] = min(roller[0], dp[tj] + a[i]);
					if (i == n)ans = min(ans, roller[0]);
					if (vis[0] == 0)hav[i+1].push_back(0), vis[0] = 1;
					//cout << "r." << 0 << " = " << roller[0] << endl;
	
					if (tj + a[i] <= 2000) {
						roller[tj + a[i]] = min(roller[tj + a[i]], max((ll)0, dp[tj] - a[i]));
						if (i == n)ans = min(ans, tj + a[i] + roller[tj + a[i]]);
						if (vis[tj + a[i]] == 0)hav[i + 1].push_back(tj + a[i]), vis[tj + a[i]] = 1;
						//cout << "r." << tj + a[i] << " = " << roller[tj + a[i]] << endl;
					}
				}
			}
			memcpy(dp, roller, 3000 * sizeof(ll));
		}
		cout << ans << endl;
		inc(i, 1, n + 2)hav[i].clear();
	}
}
/*

*/