上楼梯问题
这是一个很水的题目，就是一个斐波那契数列……
设有 (f) 数组，则 (f_i=f_{i-1}+f_{i-2}(f_1=1,f_2=2)) 。
乘车与购票
如果要抵达距离为 (x) 的一个点，可以从 (x-y) 的地方在乘一辆距离为 (y) 的车。
于是有状态转移方程：(f_i=max{f_{i-j}+a_j}) 。其中 (a) 数组为 (10) 公里及以内的车费。
小猪过河
我们可以让这只小猪从 (0) 号节点开始跳，跳到 (n+1) 号节点。
则有方程：(f_i=max(f_i,f_{i-j}-q+a_i),1le jle2) 。
再判断一下在跳的过程中的体力值即可。
排队买票
我们可以发现：一个人可以自己买票，也可以和他后面的人买票。
所以有方程：(f_i=max(f_{i-1}+a_i,f_{i-2}+b_{i-1})) 。
维修栅栏
枚举每一个“断点”（“断点”指某一个点，它后面的点一起维修）。
设 (f_i)指的是前 (i) 个木板的最小维修费用，一开始 (f_i=sqrt i) （一开始把前面的全维修了）。
则有方程：
护卫队
设 (f_i) 为前 (i) 辆车通过桥的最短时间，设 (t_{i,j}) 第 (i) -第 (j) 辆车（租车的车队）通过所需时间。
我们分析方程：
综合起来，我们就得到了方程：(f_i=min(f_{j-1}+t_{j,i}))，且要满足 (sum_{k=j}^iw_kle t) 。
为了降低时间复杂度、编程复杂度，我们可以：
-
预处理重量
定义 (W_i) 为前 (i) 辆车的总重（即前缀和，是处理这类问题非常好的方法，可以降低时间复杂度）。需要知道第 (j) 辆车到第 (i) 辆车的总重时，用(W_i-W_{j-1})就可以了；
-
预处理时间
定义 (t) 为桥的全长； (v_i) 为第 (i) 辆车的速度； (T_i) ：第 (i) 辆车通过桥所需时间； (t_{i,j}) 第 (i) 辆车到第 (j) 辆车组成的车队通过桥所需的时间；
-
(w) 数组、(v) 数组和(W) 数组一定要开 long long，否则两个较大的 int 相加会炸掉！
工作安排
设 (f_i) 为前 (i) 分钟能获得的最大的经验值。
默认在工作后才能获得经验值。容易知道，对于每一个工作，完成时间的 (f) 值就等于开始时间的 (f) 值加上工作所获得的经验值（里面取个最大值），即 (f_{S_i+E_i}=max(f_{S_i+E_i},f_{S_i}+P_i)) 。
但是要注意，对于第 (i) 分钟，它可能不是某个工作的结束时间，即 (f_i) 不会被更新。所以在枚举完前一个的结束状态时，就要用 (f_j=max(f_j,f_{j-1})) 对结果进行递推。
最长上升子序列
首先我们来讲解一下他的递推关系式：(f_i=max(f_i,f_j+1)) 。
定义 (f_i) 为：以 (a_i) 为末尾的最长上升子序列的长度。
那么 (f_i) 包含什么呢？
情况(1)：只包含它自己，也就是说它前面的元素全部都比他大；
情况2：为了保证上升子序列尽可能的长，那么就有 (f_i) 尽可能的大，但是再保证 (f_i) 尽可能大的基础上，还必须满足序列的上升。所以 (f_i=max(1,f_j+1)(j<i,a_j<a_i)) 。这里的 (1) 就是当 (a_i) 前面的数都比他大的时候，他自己为一个子序列；(f_j+1) 指的是： 当第 (i) 个数前面有一个第 (j) 个数满足 (a_j<a_i) 并且 (j<i) 这时候就说明 (a_i) 元素可以承接在 (a_j) 元素后面来尽可能的增加子序列的长度。
将 (j) 从 (1) 遍历到 (i-1) ，在这之间，找出尽可能大的 (dp_i)即为最长上升子序列的长度。（注意： (f_n) 不一定是最长的子序列。）
来源。
合唱队形
显然这是一个最长上升子序列和最长下降子序列的有机结合。
求出两者可连接的数量的最大值，那 (n) 去减即可。
友好城市
将两岸的友好城市用一个结构体存起来，以其中一个城市作为关键字进行排序，那么之后另一个城市其实会呈最长上升子序列，例如 (A) 岸城市 (1)（(A)岸城市 (1) 的意思是距离河的起点为 (1)的 (A) 岸城市）和 (B) 岸城市 (3) 之间如果开通航线，那么以后的城市都不可能向 (B) 岸城市 (1)、(2)、(3) 开通航线。那么也就呈最长上升子序列状，只要套用模板求出最长即可。
注意：一定要排序！
来源。
后记
- 感谢 L_Z_Y 对此文章提出的建议，并帮助我写了 工作安排 这一块！
- 本文有彩蛋。
- 编写不易，求点赞资瓷 ~