线性dp

数字三角形模型

【摘花生】:

状态表示：f[i][j]：从左上角到当前点的最大价值

状态属性：max

>f[i][j] = max(f[i-1][j], f[i][j-1]) + q[i];

【最低通行费】

状态表示：f[i][j]：从左上角到当前点的最小花费

状态属性：min

>f[i][j] = max(f[i-1][j], f[i][j-1]) + q[i];

【方格取数】

状态表示：f[i1][j1][i2][j2]：第一个点在[i1, j2], 第二个点在[i2, j2]的最大价值,并保证两点行走的路径一样长

状态属性：max

>int t = w[i1][j2];
>if(i1 !=i2 || j1 != j2) t += w[i2][j2]//当前两点重合，则只取一次
>for(int c = 0; c <= 1; c ++)
for(int r = 0; r <= 1; r ++)
       f[i1][j2][i1][j2] = max(f[i1][j1][i2][j2], f[i1-c][j2-r][i1-c][j2-r] + t);   

f[i1][j1][i2][j2]可以优化为f[k][i1][i2]，因为横纵之和一定，可以用k-i1 == j1等

【传纸条】

状态表示：f[i1][j1][i2][j2]：第一个点在[i1, j2], 第二个点在[i2, j2]的最大价值,并保证两点行走的路径一样长

状态属性：max

>int t = w[i1][j2];
>if(i1 !=i2 || j1 != j2) t += w[i2][j2]//当前两点重合，则只取一次
>for(int c = 0; c <= 1; c ++)
for(int r = 0; r <= 1; r ++)
       f[i1][j2][i1][j2] = max(f[i1][j1][i2][j2], f[i1-c][j2-r][i1-c][j2-r] + t);  

f[i1][j1][i2][j2]可以优化为f[k][i1][i2]，因为横纵之和一定，可以用k-i1 == j1等

证明：为什么可以使用【方格取数】一样的状态转移？

1. 假设两条路径相交：则可以左下侧和有上侧的两条不相交的路径（可能有中途相遇点）
2. 假设有中途相遇点：一定可以通过某条路径的相交点往左下或右上挪动一个位置
3. 为什么挪动一个位置不影响最后值：我们状态属性是max，所有挪动一个位置得到的价值最会变大，不会变小
4. 是否需要特判中途相遇点：不用，因为即使前面更新了中途相遇点，后面永远也不会使用这个点（可以绕得到大于或等于的值）

最长上升子序列模型

朴素：暴力

优化：二分，将当前值放入在数组中的合适的位置

【怪盗基德的滑翔翼】

求先上升再下降的最大长度

转换为某个点作为顶点时的山体最大宽度，两遍lis即可，需要两个数组记录，然后相加取max

【登山】

求先上升再下降的最大长度

转换为某个点作为顶点时的山体最大宽度，两遍lcs即可，需要两个数组记录，然后相加取max

要求严格上升和严格下降

【合唱队形】

求先上升再下降的最大长度

转换为某个点作为顶点时的山体最大宽度，两遍lcs即可，需要两个数组记录，然后相加取max

要求严格上升和严格下降

【友好城市】

转换为互相匹配的两边同增的最大长度

固定一边，求另一边lis即可

证明：为什么按照任意一遍排序都可？

假设左排序比右排序得到的结果大，那么必然存在更多的互相匹配同增最大长度，那么按照右排序也一定能找到这个组合

【最大上升子序列和】

求上升子序列的和，这里不一定时最长的。

状态表示：f[i]：以i点结尾的前i个数组成的序列最大和

状态属性：max

状态转移：枚举前面所有小于（原数组权值）i点，取最大的一个转移过来即可（n^2）

优化：

我们在找前i个点小于当前点权值同时累计和最大的点的时候，可以通过维护一个树状数组来优化，思路如下：

1. 值域较小，100000，利用下标作为单点权值， tree数组没问题（存放max）
2. 当前树状数组不再是维护前缀和，而是维护前缀最大数
3. 假设当前权值为w[i]，只需要找前w[i]-1个数中的最大数即可
4. 每次需要更新最大值，直接add即可，在add函数里是取max，所以即使传递了一个小的数，也不影响

【拦截导弹】

最小个下降子序列个数，并集等价于原数组

维护每一个下降子序列的最小值，顺序遍历原数组，若有大于q[i]，则用q[i]更新大于q[i]的最小数，若没有大于q[i]，则新开一个下降子序列

证明：为什么这样是可行的？

1. 每个数都要在某个下降子序列中，与其新开一个，不如加在别人后面（末端最小值是一样的，对后面的影响相同，这样可以少开一个）
2. 如果能加在别人后面，要加在大于q[i]的最小值后面，更大的末端值能容得下更大的后来的值，这是贪心做法

【导弹防御系统】

若干个上升子序列和下降子序列，并集等价于原数组

y总说没有更好的办法了，直接爆搜（数据范围：50）

直接爆搜会t，需要加入一些剪枝，设上升子序列个数为sc，下降子序列个数为sd，记最优解ans = n(每个数一个序列)，当sc+sd>ans则不合理，同时搜到合理方案时及时更新ans，理论上收敛在（1 << 25）以内

【最长公共上升子序列】

状态表示：f[i][j]：所有a[1~i]和b[1~j]中以b[j]结尾的max

状态属性：max

状态转移：

>f[i][j] = f[i-1][j];//不取最后一组数据
>if(a[i] == b[j]){//最后一组数据相等，可以通过f[i-1][1~j-1]中q[j] < a[i]的点转移而来
   //这里是一个循环枚举
   for(int k = 1; k < j; k ++)
       if(b[j](等价于a[i]) > b[k]) f[i][j] = max(f[i][j], f[i-1][k]+1);
>}
>/************/上述做法为三方小常，所有可以卡过，下面给出优化
>for(int i = 1; i <= n; i ++){
   int maxv = 1;//维护的是i恒定，j动态情况下的 [i-1][1~j-1]中q[j] < a[i]的点 的最大值
   for(int j = 1; j <= n; j ++){
       f[i][j] = f[i-1][j];
       if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
       if(a[i] > b[j]) maxv = max(maxv, f[i-1][j] + 1);//这一步等价于上个做法中循环k哪一行的用法
   }
>}

证明：在后面使用的时候，为什么可以使用maxv？

因为我们需要用maxv去更新别人的时候，一定有a[i] == b[j]，

所以前面那么多maxv取max的操作的控制条件a[i] > b[k]中其实就等价与b[j] > b[k]，从而保证是单调递增的，

我们要找的就是前面小于b[j]的所有b[k]中的最大值，

但是更新条件是a[i] == b[j],所以直接使用a[i]当作b[j]把后面真实的b[j]要用到的数据先处理出来，

这其实就是对原来代码的等价变形。