20230831
T1,T2
T3-LCS问题
题目描述：
给定两个长度为 \(5\ \times\ n\) 的序列 。保证 \(1-n\) 这 \(n\) 个数在 \(A,B\) 中分别出现 \(5\) 次。求 \(A,B\) 的最长公共子序列。
思路及启示：
\(1-n\) 这 \(n\) 个数在 \(A,B\) 中分别出现 \(5\) 次是非常特殊的地方，其次在枚举 \(i\) 的过程中要将求解 \(f[j]\) 的过程转化为 \(\max_{i=1}^{k-1} f[i]+1\) ，此时，我们要求的即 \(f[j]\) 的前缀最大值，可用树状数组维护。
T4-到达层数
题目描述：
思路及启示：
同余最短路
通过同余来构造某些状态（并不是用同余来跑最短路），从而达到优化时间空间复杂度的目的。
类比 luogu P5020，也可以用同余最短路跑。
这题可以设 \(dis[i]\) 表示到 \(i\) 号状态点时，所需花费最小 \(a\times x\)，也就是要达到状态 \(ax\%b==i\) 使用 \(a\) 方式的最小次数 \(x\)。
其中，我们将 \(ax%y==i\) d的状态抽象成一个点，对于这个状态 \(i\)，每取一个 \(y\)，都会对应一个新的楼层，这样 可以到达的楼层数 $=H-\left \lfloor dis[i]/b \right \rfloor $。
标签：状态,luogu,短路,同余来,20230831,dis From： https://www.cnblogs.com/Kai-benefit/p/17724922.html