kok电子竞技

1、动态规划山东省青岛第二中学 王若松1、LIS问题给出一个长度为n的序列找出一个最长的递增的子序列例如：5 1 2 4 3Ans = 3Fi = max(Fj + 1) (Aj Ai)Ans = max(Fi)O(N2)1.1、LIS的快速算法对于两个位置i, j如果Fi = Fj但是Ai Aj那么i就没用了！我们维护Gi表示Fx = i，Ax最小的一个x1.1、LIS的快速算法此时，计算Fi的方法，找出Ai Ax, Gt = x的一个最大的t二分查找！最后再更新一下G数组即可时间复杂度O(NlogN)1.2、LIS问题变形给出N个点，找出一些x、y坐标同时递增的点(不要求按照以前的顺序)。例如

2、：(5, 5) (1, 3) (2, 2) (3, 4)Ans：(1, 3) (3, 4) (5, 5)1.2、LIS问题变形经典LIS满足的条件i jAi Aj这个变形问题的条件xi xjyi yj能否类比？1.2、LIS问题变形序的应用！我们按照x坐标排序之后，就不用再考虑x坐标地增的要求了！如何处理y坐标？LISNlogN1.2.1、巴比伦塔有n种石块，石块能无限供应。每种石块都是长方体，其中第i种石块的长、宽、高分别为li、wi、hi。石块可以旋转，使得其中两维成为长度和宽度，第三维成为高度。如果要把一个石块放在另一个石块上面，必须保证上面石块的长和宽都分别严格小于下面石块的长和宽。这

3、意味着，即使两块长宽相同的石块也不能堆砌起来。求最多能用多少个石块？1.2.1、巴比伦塔将(li, wi, hi)拆成(li, wi) (wi, li) (li, hi) (hi, li) (wi, hi) (hi, wi)转化为1.21.2.2、KLO给N个积木，每个积木上面都有一个数，所有积木垒成了一个高塔。一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置。从现有的高塔中移走一些，使得有最多的积木在正确的位置。 N Aj如果Delta = Ai Aj必须满足i, j之间至少有Delta个数，也就是i j = Ai Aj变形后得到Ai i j2、Ai Aj3、Ai - i = A

4、j - j三个条件！不是LIS问题所能处理的！注意2、3已经隐含了1！把Ai看做x坐标，Ai - i看做y坐标，套用1.2的算法1.3 Dilworth定理最长A子序列=最长B序列划分A和B对立最长不降子序列=最长下降序列划分1.4、Gift有N个数，一次操作指的是把一个数拿出来然后再放回(放到的位置自己定)问最少几次操作可以将序列排序例如：2 1 3Ans=11.4、GiftAns = N LIS的长度！2、LCS给两个字符串，求最长公共子序列子序列是指的是按照顺序依次提取出若干字符例如 aba acaAns=aa2.1、LCS的优化*1、通用算法：复杂度N*M/642、排列LCS？给定两个

5、1.n的排列，求LCS2.1、LCS的优化1 3 22 1 3对于每个数记录在两个字符串的出现位置，当成点对(1, 2) (3, 1) (2, 3)选出最多的x、y坐标都递增的点1.2！时间复杂度NlogN2.2、LCS计数1问串A的一个子序列，串B的一个子串，两者相等的有多少例如：A=abac B = bacAns=82.2、LCS计数1Fij表示A串的前i个字符，B串前j的字符的LCS的数量Fij= Fi - 1j - 1 (when Ai=Bj), + Fi - 1j2.2、LCS计数1可能的问题？A可能是空串！加一个常数维表示A串是否已经至少取了一个字符2.2、LCS计数2求两个串LC

6、S的数量例如：A=AAB B=ABAns=22.2、LCS计数2在经典做法的基础上，加入计数的部分Gij表示A串前i个，B串前j个，取到Fij的方案数考虑Gij的计算2.2、LCS计数2Ai=Bj时Gij=Gi-1j-1 +Gi-1j (当Fi-1j=Fij) +Gij-1 (当Fij-1=Fij)AiBj时Gij=Gi-1j (当Fi-1j=Fij) +Gij-1 (当Fij-1=Fij)2.2、LCS计数2问题？如果Ai不等于Bj, Fij = Fi 1j - 1此时Gi - 1j - 1在Gi - 1j, Gij - 1中被计数了两次！解决方案？如果Ai != Bj, Fij = Fi

7、- 1j - 1Gij = GI - 1j+Gij - 1 GI - 1j - 13.1、背包问题1、部分背包2、0/1背包3、完全背包3.2、消失之物给定N个物品。对于每个物品i，我们要计算出，在不使用这个物品而使用其他N-1个物品的情况下，装满j(1=j=M)背包的方案数。N, M = 10003.2、消失之物在原问题解法的基础上，加一个Gij,表示在不用i物品的前提下，装满j容量背包的方案数Gij = Fnj Gij Ai3.3、Elect给定N个数，选出一些，要求他们的和最大。并且删掉任何一个滞后，其他数的和不能大于总数的一半。N, SUM = 10003.3、Elect第二个条件比较

8、困难我们发现：如果最小的数已经满足这个条件了，其他的数一定满足了！考虑从大到小做背包！Ans = Ai + Fi - 1SUM / 24、数位统计求L.R中的数量不少于的数量的数的个数求1.L中的数量不少于的数量的数的个数4、数位统计预处理统计Fij 表示长度为i的数，比多j的数的数量统计Gij 表示长度为i的数，比多j的数的数量(不允许前导零)4、数位统计统计过程R = 987654321从高到低一位一位统计800000000-899999999.000000000-099999999900000000-909999999970000000-979999999980000000-980999

9、999986000000-986999999每一段的统计方法？利用之前的DP！5、矩阵优化递推式以Fi = Fi - 1 + Fi - 2为例1, 1, 2, 3, 5, 8, 135、矩阵优化递推式1、矩阵乘法的定义两个N*N的数组A, BC = A * B等价于Cij = Aik * Bkj(1 = k 2, 2-2 (Fi+1 = Fi + Fi-1)连边2-1 (Fi = Fi)5、矩阵优化递推式5、细节问题最后的矩阵的意义？(F1, F2)(F2, F3)(F3, F4)表示的是这些项跟初始项的关系Fn = A11 * F1 + A21 * F25、矩阵优化递推式5、细节问题更加复杂度的递推式？Fi =a1*fi - 1 + a2*fI - 2 + 增加矩阵的大。∠凳苛佣嗵醣弑硎荆〕Ｊ睿咳∫桓龅阕庞美醇锹汲Ｊ