NOIP2024集训Day22 DP常见模型3 - 区间

NOIP2024集训Day22 DP常见模型3 - 区间

A. [SCOI2003] 字符串折叠

因为前面折叠了会对后面产生影响，所以很显然不能贪心。

考虑区间DP。

定义 \(f_{i, j}\) 表示 \(i\) 到 \(j\) 范围内可以折叠到的最短长度。答案为 \(f_{1, n}\)。

状态转移：对于 \(f_{i, j}\)，使用区间DP惯用套路，枚举 \(k\)，那么 \(f_{i, j}\) 就有两种情况：

1. 直接由 \([i, k]\) 和 \([k + 1, j]\) 拼接起来
2. 把 \([i, k]\) 作为模板串，将 \(s_{i, j}\) 写成 \(x\) 个 \(s_{i, k}\) 的形式，但前提是此举可行（每次枚举 \(k\) 的时候暴力判断）

最坏时间复杂度为 \(O(n^4)\)，但其实远远达不到。

B. [ABC221G] Jumping Sequence

非常巧妙。

将坐标系顺时针旋转 \(45^\circ\)，也就是说把曼哈顿距离转化成切比雪夫距离，\((X, Y) \rightarrow(\dfrac{X+Y}{2}, \dfrac{Y-X}{2})\)，不用考虑 \(\sqrt{2}\) 的问题，因为在旋转 \(45^\circ\) 之后整个距离都会变成原来的 \(\dfrac{\sqrt{2}}{2}\) ，然后再整体除以 \(\sqrt{2}\)，消除 \(\sqrt{2}\) 带来的影响。

这样一来，我们就可以把横坐标和纵坐标独立开来，方便处理。

于是问题转化为：求序列 \(C_i\)，使得 \(\sum C_i\cdot D_i = s(s = \dfrac{X+Y}{2}/\dfrac{Y-X}{2})\)。

分开讨论，分别对横坐标和纵坐标进行处理。

再进行一次转化：设 \(\sum D_i = sum\)，求出序列 \(C_i\) 等价于在 \(D_i\) 中选取若干个数，使得 \(\sum C_i = \dfrac{sum - s}{2}\)。

于是就变成了01背包，用 bitset 优化一下即可。

F. [CF500F] New Year Shopping

线段树分治。

按时间将询问离线，然后按时间建线段树，把物品的影响加到 vector，dfs线段树，合并背包即可。