《算法设计与分析》期末复习
导弹拦截
https://www.luogu.com.cn/problem/P1020
定义状态 \(f(i)\) 为 \(1 ~ i\) 区间内的最大导弹拦截数量
有状态转移
\[f(j) = max { f(i) } + (a[j] <= a[i]) \]直接赤裸裸的做状态转移，时间复杂度预计在 \(O(n^2)\)，空间复杂度在 \(O(n)\)
考虑对于一组序列 $ { a_1, a_2, ..., a_n} $
维护的状态数组中提取出的最长不下降子序列为 $ {1, 1, ..., 2, ..., k} $
实际上对于状态数组中最后一段连续的值相同的序列，选择这段序列中任何一个对应的导弹作为结尾（也就是最后一个打下来的导弹）都合法，但是选择最高的那个必然是最优的
那么可以定义 $ cnt(1 ... num) $ 记录我们的答案，显而易见的是 $ cnt $ 具备一个不怎么严格的单调性
那么对于下标 $ j $，如果 $ a(j) <= a(cnt(num)) $，则 $ f(j) = f(cnt(num)) + 1, cnt(num + 1) = a(j)$
否则二分查找最大的元素 \(a(cnt(k))\) 满足 $ a(cnt(k)) <= a(j) $，把 $ cnt(k) $ 替换为 $ j $
第二问涉及到 Dilworth 定理在偏序集上的证明
打鼹鼠
https://www.luogu.com.cn/problem/P2285
容易证明，起点必然在某一个鼹鼠的出生位
容易想到以下状态转移
\[f(i, j, k) = max { f(i + dx, j + dy, k - 1) } + (a(i, j) == k） \]空间上太复杂，算法实现上也不做人，必然涉及到记忆化搜索，考虑简化状态转移
实际上，对于题目的需求，坐标本身描述空间的属性意义不大，仅仅规定了从一个状态到另一个状态之间转移要付出的代价
完全可以将二维点抽象成按时间排列的一维的序列，两两之间的转移代价由 $ | x_i - x_j | + | y_i - y_j | $ 唯一确定
那么这题又变成了最长子序列的问题了，只不过不再是由“不下降”或者“不上升”这样的关系规定，而是由 $ | x_i - x_j | + | y_i - y_j | < k_i - k_j $ 这样的关系来规定
那么有状态转移：
\[f(i) = max { f(j) } + (| x_i - x_j | + | y_i - y_j | < k_i - k_j) \]初始状态需要枚举起点：
\[f(k) = 1 \] 标签：状态,cnt,...,max,序列,线性,动态,规划,转移 From： https://www.cnblogs.com/sysss-blogs/p/18213380