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

题目大意：

CF1601B Frog Traveler
题目大意，有n个点（级别为3e5），第i个点离地平线距离为i，向上可以往上跳1-a[i]距离，但如果是跳到这个点则会下滑b[i]距离，你一开始在离地平线为n的位置，现在需要输出一个跳法让你能跳到地上。

解：

要能跳到地上首先你得跳到一个能跳到地上的点上，有子问题出现，判断为线性dp。
要想到达那个能跳到地上的点，你必须跳到它上面的某个点并滑下来，因此我们可以把整个过程看作是一条树上的岔路，如果有m个点可以直接跳到地面上，那么同样有m个点可以滑到这些点上，我们应该选哪个呢？当然是最低的那个可以滑到能直接跳到地上的点，因为如果我能到达更高的点，我也能到达这个最低的点，但能到达最低的点的点并不能直接跳到高的点。在选定了要跳的点之后，我又会出现m个能够跳到这个点上的点，于是我会再次重复这个过程，直到第n个点，也就是我的起始点也能跳到需要跳到的点上。因为我的路径是固定的所以直接保存就行。
实际上整个过程直接模拟就行，并不需要用到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
82
83
84
85
86
87

#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 300005
#define mdl 1000000007
#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 slip[maxn],a[maxn],ans[maxn],fromto[maxn],slipamt[maxn],rcd[maxn];
int main() {
	cfast;
	int n;
	cin >> n;
	ll target = 0,tmp=0;
	ll step = 0;
	inc(i, 1, n + 1) {
		scanf("%lld", &a[i]);
	}
	inc(i, 1, n + 1) {
		ll d;
		scanf("%lld", &d);
		slip[i + d] = i;
		slipamt[i] = d;
	}
	inc(i, 1, n + 1) {
		int target = i - a[i];
		if (slip[i] > rcd[target]) {
			rcd[target] = slip[i];
			fromto[target] = i;
		}
	}

	int f = 0;
	while (f==0) {
		step++;
		ll tans = -1,tmp1=tmp,tar1=target;
		for (int i = tmp; i <= tar1; i++) {
			if (fromto[i]) {
				if (fromto[i] == n) {
					ans[step] = tar1;
					f = 2;
					break;
				}
				ll slp = slip[fromto[i]];
				if (target <= slp) {
					target = slp;
					tans = i;
				}
			}
		}
		if (f == 2)break;
		tmp = tar1;
		if (tans != -1) {
			ans[step] = tar1;
		}
		else { f = 1; }
	}
	if (f == 2) {
		printf("%d\n", step);
		inc(i, 1, step + 1) {
			printf("%d ", ans[step+1-i]);
		}
	}
	else {
		printf("-1");
	}
}
/*
3
4 12 6 
*/