下面一系列的线性dp问题更依赖闫氏dp分析法的发挥。

这里记录几条经验：

1. 当状态计算方程中，在遍历时出现了 f[i-1] 的字样，那么数组下标就要从1开始，来防止负数下标和越界。

2. 状态表示，我们划分集合的原则为 “不重不漏”：不重复，不遗漏。

   当状态属性 要求取 sum 集合的总和时，不重复的原则很重要。

   但状态属性取 max/min 集合的最值时，集合间元素发生重复不会影响结果。

   举个例子： 1,2,3

   • 求最值：max = max(max (1,2) , max (2,3) )。 这里2发生了重复，但不影响最大值3的求取。

   • 求总和：sum = sum(sum (1,2) , sum(2,3) )。 这里2发生了重复，影响了总和的求取（2被加了两次）

3. 状态表示分为三部分：

   • 集合的维度：一维数组 f[i] 能求出答案吗？不能的话就用二维数组f[i] [j] ，还不行就三维。
   • 集合的表示：每个集合，它的意义是什么？这个意义要能概括题目的所有情况。
   • 集合的属性：求sum还是max？属性有时会影响状态计算方程的展开。

4. 一个简单的数学模型：

   集合A：a1,a2,a3 … an

   集合B：a1+w,a2+2, … an+w

   则有：min(A)+w = min(B)

   或 ：min(A) = min(B) - w

5. C++语言，一秒处理数据大小为 10^{8左右，尽量把复杂度控制在10}7，最多10^8