算法合集之《浅谈信息学竞赛中的“压缩法”》.ppt

压去冗余缩得精华——浅谈信息学竞赛中的“压缩法”安徽周源

引子压缩软件？本义：加以压力,以减小体积、大小、持续时间、密度和浓度等压缩法除去冗余信息，留下精华，以减小问题的规模压缩法？？

压缩法的定义将集合S作为内外隔绝的包裹打包压缩略去了包裹内部的冗余信息，从而简化问题S

[例二]球队问题(经典问题)篮球队的球员通讯图，(B,A)表示B能通知A教练需要通知所有人一条消息最少需要告诉几个人？本例中最少为2人如A,F等等ABCDEFG亲自

[例二]球队问题(经典问题)使用压缩法，“压去”不必要的信息求出强连通分量S1,S2,S3…“压缩”每个分量?新点保留分量间连边情况ABCDEFGS1S3S2

[例二]球队问题(经典问题)压缩转化后的新图简洁：没有环的存在无入度的点：必须亲自通知有入度的点：必定可以由队员通知结论：答案为压缩后图中无入度点的数目S1S3S2

压缩法的要点1.可压缩性集合S内部各个元素之间的联系不会和外部元素相互作用而影响到问题的结果即可压缩[例二]中：强连通分量内球员的通讯情况不会影响球员是否得知消息状态的恒等性舍去分量内球员的通讯情况，压缩为新的节点

压缩法的要点压：可以压去存在的冗余信息(可压缩性)缩：保留S作为一个点与外部信息的联系(替代法则)2.替代法则用什么样的形式表现出精华部分的内容[例二]中用一个点替代一个集合用相同形式的有向边代替原来集合的内外联系

压缩法的应用压缩法在很多竞赛试题中有巧妙的应用[例四]欧元兑换(BOI2003euro)[例五]合并数列问题(ZOJp1794)[例五]合并数列问题(ZOJp1794改编)

[例五]合并数列问题(ZOJp1794改编)有K个数列a1,1,a1,2,a1,3…a1,n1a2,1,a2,2,a2,3…a2,n2…ak,1,ak,2,ak,3…ak,nk如K=3时35-45-106-35-104-515-205-13-42-6

[例五]合并数列问题(ZOJp1794改编)如K=3时要求将这些数列归并成为一个新的数列S35-45-106-35-104-515-205-13-42-65-104-55-13-42-635-45-1015-206-3S：且新数列S的部分和中最大的数最小最大部分和为7有K个数列a1,1,a1,2,a1,3…a1,n1a2,1,a2,2,a2,3…a2,n2…ak,1,ak,2,ak,3…ak,nk数据范围K≤100000N=n1+n2+…+nk≤100000

初步分析普通动态规划算法时间复杂度O(K*NK)显然无法承受使用“压缩法”

观察压缩要点1.可压缩性观察：最优串中的一些子串就是原串的子串反之：若原串的子串满足性质P即为S的子串该子串可压缩，P就是可压缩性35-45-106-35-104-515-205-13-42-6最优串S：5-104-55-13-42-6……5-104-55-104-55-13-42-65-13-42-6

观察压缩要点2.替代法则若存在一段可压缩的子串u替代法则保存u内元素与外部因素间的联系a)u的最大部分和(即相对峰值)可能是S的最大部分和b)u的总和对以后的部分和产生影响相对峰值总和替代法则u的部分和用连续的两个数a,b代替a为u的相对峰值b为非正的修正值(a+b)为u的总和ab(a+b)a一“对”(couple)

寻找可压缩性：第一阶段压缩[定理5.1]某子串c1,c2,…,cp可压缩当总和非正其余部分和为正数c[证明5.1]调整法若c在S中不连续出现则可调整具体方法参见论文

寻找可压缩性：第一阶段压缩35-45-105-104-515-205-13-42-6[定理5.1]某子串c1,c2,…,cp可压缩当总和非正其余部分和为正数压缩转化后每个数列的前一部分每一“对”的总和都是负数（或0）正数后有一个绝对值更大的负数每个数列的后一部分一串任意部分和为正的子列作为对称问题考虑(9-10)(7-8)6-3

寻找