腾飞 dp【坚决不能咕！！！】

错排计数

给定 \(1\sim n\)，求有多少种排列使得 \(p_i\ne i\)。

令 \(f_n\) 代表问题规模为 \(n\) 时的答案。

考虑如何转移到 \(f_n\)。

我们假设 \(n\) 这个数放在了第 \(i\) 个位置，此时 \(n\) 这个位置按照是否为 \(i\) 可以出现两种情况，我们分类讨论。

假设 \(i\) 放在了 \(n\)，那么我们只需让 \(1\sim i-1\) 和 \(i+1\sim n-1\) 错排。发现这个东西就是 \(f_{n-2}\)。

假设 \(i\) 没有放在 \(n\)，那么我们会有一个 \(p_n\ne i\) 的限制，综合之前的限制 \(p_1\ne 1,\cdots\)。我们发现这个 \(i\) 没什么意义，只是 \(n-1\) 个限制中的一种。发现此时就是 \(f_{n-1}\)。

综合起来就是 \(f_n=(n-1)(f_{n-1}+f_{n-2})\)。

链上最大独立集

有 \(v_1,v_2,\cdots,v_n\)，限制选了 \(v_i\) 就不能选 \(v_{i+1}\)，求能选的最大权值和。

令 \(f_i\) 代表最后一个选 \(v_i\) 的答案。

此时 \(v_{i-1}\) 不能选，发现转移 \(f_i=\max\limits_{1\le j\le i-2}{f_j}+v_i\)。

维护一个前缀max即可。

但是这样太麻烦了。

令 \(f_i\) 代表最后一个选的位置 \(\le i\) 的最大值。

\(f_i=\max(f_{i-1},f_{i-2}+v_i\times[v_i>0])\)，发现这个东西很对。

LIS

令 \(f_i\) 代表以 \(i\) 结尾的最长LIS的长度。

回想一下 \(n^2\) 的转移：\(f_i=\max_{1\le j<i,a_j<a_i}{f_j}+1\)。

假设现在有 \(f_j=l\)，我们实际上转移时并不关心这个 \(j\) 到底是多少，关心的是 \(a_j\) 是多少。

我们发现对于所有 dp 值为 \(l\) 的 \(i\)，一定是 \(a_i\) 单调下降，不然就会出现一个地方的 dp 值可以变为 \(l+1\)。

令 \(f_i\) 代表最后一个 dp 值为 \(i\) 的地方上 \(a_i\) 是多少。

发现 \(f_i\) 是单调上升的。因为如果 \(f_l\le f_{l+1}\)，由于刚才的结论，你 \(f_{l+1}\) 从哪转移过来？

二分处理这个东西即可。

P3558

link

首先发现把一个数减到小于 \(-1\) 或大于 \(1\) 没什么用。