Dividing

Dividing Subsequence 这道题与最长公共子序列类似，可以先去水一水那道题。 题意 本题就是让你从 \(p\) 里面选出一个子序列 \(b_i\) 和 \(q\) 里面选出一个子序列 \(a_i\)，我们要使 \(b_i\) 是 \(a_i\) 的倍数。 解法 本题直接用动态规划，是 ......

给一个长为 $n$ 的正整数数组 $a$ ，在一步操作中，你可以选择任一个数并且 $add\ 1$ 。要求最多执行 $2n$ 步操作使 $a$ 满足 $\forall i, i \in[1, n - 1], a_{i} \nmid a_{i + 1}$ 。输出任一个在操作数限制内可以得到的合法数组。 ......

这个分治策略其实跟整体二分差不多，但是它的应用面比较单一和具有针对性。 通常是 $dp_1,dp_2,dp_3,...,dp_n$ 只有 $O(d)$ 段。然后我们通过分治来看 $dp_i=v$ 的应该是哪一段。 ``` def solve(l,r) if dp(l)==dp(r) fill dp( ......

丢一发好理解又好写的线段树优化dp。 [题目传送门](https://www.luogu.com.cn/problem/P1545 "题目传送门") ### 简要题意 给定一个长为 $l$ 的线段，求出尽量少的不相交区间覆盖整段线段，要求题目给的所有子区间只被 $1$ 个区间覆盖。 ### 分析 显 ......