线性dp 课后练习

1. [ABC354F] Useless for LIS

提示： $l[i]$ 表示原序列中 $a_1...a_i$ 以 $a_i$ 结尾最长上升子序列长度，$r[i]$ 表示原序列 $a_i...a_n$ 以 $a_i$ 开头最长上升子序列长度，如果满足 $LIS==l[i]+r[i]-1$ , $a_i$ 就可以是 LIS 的一个元素，否则不在 LIS 中。

$l[i]$ 和 $r[i]$ 可以使用 二分优化 或 线段树优化 在 $O(n\log n)$ 的复杂度内求得。

2.ABC369F Gather Coins

思路：直接求会MLE,转化为 LIS.按 x 排序，求 y 的 LIS

3.CF2096C Wonderful City

思路：行列操作互不影响，可以分开处理。每行或列最多操作一次，那么就是操作或者不操作，相邻行之间或者列之间不能同时操作，转换为线性dp。

4.abc403D - Forbidden Difference

思路：题目要求删除最少得数，使得剩下数不存在差等于 d 的情况。可以将差为 $d$ 的序列单独分出来，每个数删或者不删，转换为线性 dp 。注意需要特判 $d=0$ 的情况。

5.abc404_e Bowls and Beans

分析：一次可以移动多个豆子，那么从后向前移动，转换为线性 dp 。

学习完毕

{{ select(1) }}

• YES
• NO