Posted on 2011-03-19 22:38
Mato_No1 阅读(889)
评论(0) 编辑 收藏 引用 所属分类:
树状数组 、
AHOI
依照CLJ神犇的指示，最近本沙茶决定开始被数据结构题虐……先找来了省内的一道题（就是这道囧）……
题目大意：求两个长度为5N的序列的最长公共子序列长度，在两个序列中，整数1~N分别都出现5次。1<=N<=20000。
【注：本沙茶一开始用线段树的，后来在看了CLJ神犇的标程（Orz！！）之后终于明白了树状数组解法囧……】
LCS问题的朴素时间复杂度为O(NM)。对于本题显然需要优化。
观察LCS的转移方程：
F[i][j] = F[i-1][j-1]+1（当A[i]==B[j]时）
F[i][j] = max{F[i-1][j], F[i][j-1]}（当A[i]!=B[j]时）
可以将F用滚动数组来表示，即设F'为上阶段的F（即F[i-1]），则本阶段的F（即F[i]）可以由F'求得：
F[j] = F'[j-1]+1（当A[i]==B[j]时）
F[j] = max{F'[j], F[j-1]}（当A[i]!=B[j]时）
进一步，这个F'其实都不用记录，只需在每一阶段更新一遍F即可：
F[j] = F[j-1]+1（当A[i]==B[j]时）
F[j] = max{F[j], F[j-1]}（当A[i]!=B[j]时）
不过需要逆序更新（保证F[j-1]是上一阶段的而不是本阶段的），这与01背包有点像。
由题意可以发现，A[i]==B[j]的出现次数极少，在每阶段中只会出现5次！我们可以预先求出这5个地方的值，然后对于其它的F[j]，其在本阶段的值其实就是它前面的最大值（max{F[1..j-1]}），又因为我们最后只需知道F[N']（N'=5N，即序列长度）即可，故可设计出以下算法：
一开始F[1..N]均为0，然后将以下内容执行N'次，第i次：
（1）求出B序列中与A[i]相等的5个元素的位置，设为S[1..5]；
（2）依次更新F[S[5..1]]，每个都更新为它前面的最大值加1（很容易知道为神马），其它的值暂时不管；
N'次执行完后，整个序列中的最大值就是F[N']的值。由于这个算法中出现的主要操作是改动一个指定位置元素的值和找一个前缀区间中的最大值，因此可以采用树状数组，时间复杂度O(NlogN）（线段树必TLE）。
【总结：在本题中使用了一种“推迟更新”的方法，即需要更新一个值时，先暂时不理它，等到需要引用到它的时候再更新。这种方法最常见的应用就是线段树的结点标记。不过要注意的是，如果该值的推迟更新会对它后面要更新的值带来问题（也就是，这些后更新的值需要引用该值的新值），就不能使用这种方法。在本题中，其它位置的值的改变只与这5个特殊的位置有关，与其它因素无关，故可以使用这种方法。】