打卡第一天！
1.数字三角形模型（动态规划）方法：从集合角度来考虑DP问题——y氏DP法
状态表示：集合（根据题目自己思考）and属性（数量/Max/Min）
状态计算：集合的划分
重要的划分依据：“最后”
重要的划分原则：1、不重复 2、不漏
摘花生问题1015. 摘花生 - AcWing题库
要注意边界的分类讨论和求最小值时，状态表示为正无穷。
活动 - AcWing
方格取数问题用三维的数组表示，特殊状态k为步数，步数相同时，如果两条路线的横坐标+纵坐标相等，则两条路径的重合。k = i + j ，横纵坐标之和。
1027. 方格取数 - AcWing题库
传纸条问题右下角往左上角传可以看作左上角往右下角传，转化为方格取数问题。
275. 传纸条 - AcWing题库
总结题谱：
90%的dp问题都能转化为最短路问题，拓扑图可以转化为dp问题。记住模型，到相似题目就会有更清晰的思路，不会到无从下手。
2、最长上升子序列模型（LIS）打卡第二天！
因为是一维的数组，所以状态表示只需要一维。
因为状态表示为以倒数第一个数结尾，所以考虑状态计算的时候，从倒数第二个数考虑（空的情况），是序列里只有a[i]的情况。
都有共同元素a[i]，以a[k]结尾的最长上升子序列正好是f(k)，所以等于f(k) + 1，且只有在a[k] < a[i]时成立。
基础的LIS模板。
895. 最长上升子序列 - AcWing题库
怪盗基德滑翔翼往左：最长上升子序列。往右：最长下降子序列（逆向最长上升）
1017. 怪盗基德的滑翔翼 - AcWing题库
登山状态表示时从顶点考虑，a[k]被算了两次，所以重复了，-1。
1014. 登山 - AcWing题库
合唱队形登山问题的对偶问题。最少多少出列就是最多留下多少的意思，用总数减去结果即可。
482. 合唱队形 - AcWing题库
友好城市控制住自变量，去思考因变量，散列，转化为一维问题。把岸两边的数都拍好序，确保连接的航道是友好航道，有一个不是上升的就会相交，因此是最长上升子序列模型。思考过程很难（能想到LIS，基本上就解决了）
1012. 友好城市 - AcWing题库
最大上升子序列和比较简单，就是模型求个数和变成求值的和
1016. 最大上升子序列和 - AcWing题库
拦截导弹DP + 贪心（基于基础课的最长上升子序列（II））
1010. 拦截导弹 - AcWing题库
也可以用贪心 + 贪心来做，Lower_bond和upper_bond。
lower_bond : (begin , end , a ) 返回第一个大于等于a的数组的下标
upper_bond : (begin , end , a) 返回第一个大于a的数组的下标
lower_bond : (begin , end , a , greater () ) 返回第一个小于等于a的数组的下标
upper_bond : (begin , end , a , greater () ) 返回第一个小于a的数组的下标
include #include using namespace std;const int N = 1100;int f[N] , g[N];int main(){int len = 0 , cnt = 0;int a;while(cin >> a){//pos1 表示以a结尾的最长下降子序列长度int pos1 = upper_bound(f , f + len , a , greater ()) - f;if (pos1 == len)f[len ++] = a;//开创一套新的导弹系统elsef[pos1] = a; //使a成为当前导弹系统的最后一位int pos2 = lower_bound(g , g + cnt , a) - g;if (pos2 == cnt)g[cnt ++ ] = a;elseg[pos2] = a;}cout > m;for(int i = 0 ; i < n ; i ++ ){int v , w , s;cin >> v >> w >> s;memcpy (g , f , sizeof f);for(int j = 0 ; j < v ; j ++ ){int hh = 0 , tt = -1;for(int k = j ; k