有趣的矩阵乘法

(为方便,下文中“大号宝石”代指连续的$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)$级别的算法,我们接下来考虑矩阵乘法优化这个式子。

简单递归

首先我们如果要消灭一段区间$[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$的代价将其摧毁。
DP

一道有点套路化的网格图上$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])$

DP

前言

单调队列一种非常经典的将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$),然后我们就可以写出如下的程序:

DP