开场 10 分钟就有人过的 1D ，你值得拥有！

$\texttt{swap(B, D)}$ 警告。

瞎搞DP

CF出了H没出G 菜的真实

发现$k$从$\texttt{E}$题的$100$变成了$O(10^{12})$，考虑与$k$复杂度无关的做法。

我们考虑$f_{i, j}$表示以$s_i$开始，本质不同的长度为$j$的子序列数量。

哈希 + 二分 + DP

首先看到题面，很容易想到一个$DP$，令$f[i]$为划分到$i$为止的方案数。

然后朴素的暴力转移是$O(n^2)$的，非常显然一个状态$i$能够转移到的$j$是一段连续的，进而想到使用前缀和优化。

有趣的矩阵乘法

（为方便，下文中“大号宝石”代指连续的$m$个分裂出来的宝石，“小号宝石”代指未分裂的单个宝石）

首先，我们观察这题，考虑$DP​$，设状态$f_i​$表示已经取了$i​$个单元的方案数的不难推出一个朴素的$O(n^2) DP​$方程$f_i = \displaystyle\sum_{i - j \geq m} f_j +1​$（可以理解成上一个大号宝石放的位置，最后一个$1​$即为全部用小号宝石填满的方案）

我们再仔细看看这个式子，加个前缀和，不难优化到$O(n)$，然而数据范围$n \leq 10^{18}$，这让我们考虑$O(\log n)$级别的算法，我们接下来考虑矩阵乘法优化这个式子。

本篇题解讲述的为非完美做法，但是可以骗到96分

说实话我在网上找了好久结果都是这个$O(n^2)$的非正解树型$DP$

听说有个$O(N)​$的正解在某篇论文里？

算了反正我也看不懂

所以我接下来就介绍一下这个$O(n^2)$的树型$DP$吧QwQ

顺手丢一下我学习的这篇blog​吧

简单递归

首先我们如果要消灭一段区间$[l, r]$，我们可以有三种选择：

• 如果$[l, r]​$区间内没人，那么直接花费$A​$的代价将这段摧毁
• 如果$r > l​$（即这段区间长度$>2​$），可以选择把它切割成$\left[ l, \lfloor \frac{l + r}2\rfloor\right]​$ $\left[\lceil \frac{l + r}2\rceil, r\right]​$两段
• 如果$[l, r]$区间内有人，直接花费$b (r - l + 1)x$的代价将其摧毁。

其实我很想吐槽这题

我比赛的时候疯狂$\text{WA on test 16}​$

然后死活找不出来哪儿错了

我觉得我数组开小了

于是我开到$MLE$都没有过掉

最后一看

被一个n = 2的点卡掉了……

才出4题，罚时爆炸，上黄失败，掉分哭唧唧

一道有点套路化的网格图上$DP$QwQ

我们用$f_{min}[i][j][0]$表示线头在$(i, j)$这个点的时候，线的方向朝__下__，我们能取到的最小的拐弯次数、用$f_{min}[i][j][1]$表示线头在$(i, j)$这个点的时候，显得方向朝__右__，能够取到的最小的拐弯次数

同理，我们用$f_{max}[i][j][0]$与$f_{max}[i][j][1]$表示线头在$(i, j)$位置是线朝下和朝右能够取到的最大的拐弯次数。

接下来，对于有障碍的点，我们直接不处理

显然，答案分别为$\max(f_{max}[n][m][0], f_{max}[n][m][1])$与$\min(f_{min}[n][m][0], f_{min}[n][m][1])$

前言

单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式，在一个点可以更新一个范围的时候可以发挥很大作用。

记得当年NOIp2017我考PJ（那年的T4考到了单调队列），当时还不会，在考后听教练讲了一遍之后仍旧处于懵逼状态，大概1个月前照着题解打了一遍，但是到了现在已经忘得差不多了QwQ，于是写了一遍优化过的多重背包来练练手。

竟然没有人写题解2333那本蒟蒻就来$H_2O$一篇吧

首先，看完题面不难想到DP，之后再看数据范围考虑$O(N^3)$DP，之后瞎搞一通可以想到

$f[i][j]$表示在前$i$个里面经历$k$次出逃可以取到最少的修改数

那么接下来我们就发现$f[i][j]$可以影响的范围为$f[u][j+1]$($i < u ≤n$)，然后我们就可以写出如下的程序：