国家集训队2004论文集 胡伟栋

湖南省长沙市长郡中学胡伟栋减少冗余与算法优化减少冗余与算法优化要提高算法的效率，必须减少算法中的冗余算法的目标：用最少的时间解决问题最高的效率冗余：多余的或重复的操作高效率在搜索、递推、动态规划……中，都可能出现冗余例1：整数拆分——问题描述将整数N拆分成若干个整数的和，要求所拆分成的数必须是2的非负整数幂的形式。问有多少种拆分方案？如果两个方案仅有数的顺序不同，则它们算作同一种方案。当N=5时，可以拆分成下面的形式：5=1+1+1+1+15=1+1+1+25=1+2+25=1+45有4种拆分方案。例1：整数拆分——样例例1：整数拆分——递推的建立用F[i,j]表示i拆分成若干个数，其中最大的数不超过2j的拆分方案数。递推方程：递推的表示：目标：2[,log]FNN最大数是最大数小于[0,]1Fj[,0]1Fi[,]Fij[,][2,][,1]jFijFijFij[2,]jFij[,1]Fij2j2j(初始值)例1：整数拆分——递推复杂度复杂度：时间复杂度：O(Nlog2N)空间复杂度：O(Nlog2N)22loglogiN[,][2,][,1]jFijFijFij1≤i≤N1≤j≤≤JI123012345678M=3,N=8BF[i,j-1]AF[i,j]例1：整数拆分当N=2M(M是非负整数)时实际要计算的点数：1+2+22+23+24+……+2M-1=2M-1=N-1F[i,j]ij[2,]jFij——递推中的冗余1=202=214=22C当j=M-k时，第j行要计算的点数为2k。例1：整数拆分——减少冗余当N=2M(M是非负整数)时当i=x时，第i列要计算的点数与x的二进制表示中最末的0的个数相等12102112100210121102111210002时间复杂度：O(N)JI123012345678每列要计算的点是最下方连续的若干个点需要计算的点已知点不必求出的点JI123012345678例1：整数拆分——减少冗余当N=2M(M是非负整数)时在所有F[x,j](j一定,x为变量)中，只要存储x最大的一个即可。未知点处理中的点已知点不必求出的点[,]Fij[,1]Fij[2,]jFij空间复杂度：O(log2N)例1：整数拆分——减少冗余JI123012345678当N≠2M时，可转化成N=2M的形式求解例1：整数拆分——减少冗余设N=2M-r(2M-1N2M)0000000r目标F[N,M-1]F[N,M]例1：整数拆分——小结冗余时空复杂度较高去除冗余后时空复杂度相对很低去除冗余优化本题的关键例1：整数拆分——最后的思考更优秀的算法？Exploring公式？...例2：最大奖品价值——问题描述有N+2级楼梯，分别用0至N+1编号，第1至N级楼梯上每级都放有一个奖品，每个奖品都有一个正的价值。如果某人从第0级开始，向上走M步正好到达第N+1级楼梯，他将得到所走过的楼梯上的所有奖品，否则他将一无所获。问能得到的奖品价值的和最大是多少？当然，一步不可能走太多级楼梯，假设每步最多上K级，即最多从第i级走到第i+K级。例2：最大奖品价值——数学模型有一列数a0,a1,a2,…,aN,aN+1其中a0=0a1,a2,a3,…,aN0aN+1=0从中选M+1个数…,，使1)0=i0i1i2…iM=N+1；2)i1-i0,i2-i1,i3-i2,…,iM-iM-1≤K3)…最大012iiiaaaMia012,,iiiaaaMia例2：最大奖品价值——动态规划状态表示：用F[i,j]表示走i步到达第j级楼梯能得到的奖品的价值和的最大值F[i,j]=max{F[i-1,x]}+ajj-k≤xj时间复杂度：O(NMK)例2：最大奖品价值——规划中的冗余从F[i-1]到F[i]的转移f1[j]表示F[i-1,j]f2[j]表示F[i,j]f1[j-k-1]f1[j-k]f1[j-k+1]…f1[j-3]f1[j-2]f1[j-1]f2[j-1]f2[j]maxmax例2：最大奖品价值——减少冗余动态的考虑：每次要求的f1的一段都是变化的每次会加入一个新元素每次会删除一个元素堆静态的考虑：每次都是找f1中连续的一段线段树log2Klog2KNMNM编程复杂度O()O()高例2：最大奖品价值——减少冗余f1[j-k]f1[j-k+1]…f1[a]…f1[b]…f1[j-1]f1[j]abjf1[a]≤f1[b]对于任意abj只有f1[a]f1[b]时，f1[a]才有用f2[j]f1[a1]f1[a2]f1[a3]……f1[ar]maxj-k≤a1a2a3……arj例2：最大奖品价值——减少冗余数据结构：删除第一个元素新增元素到最后一个位置，并维护这个数据结构使它保持递减的性质线性表*队列堆栈f1[a1]f1[a2]f1[a3]f1[a4]f1[a5]f1[a6]f1[a7]f1[a8]xx例2：最大奖品价值——时间复杂度O(NM)时间复杂度例2：最大奖品价值——小结O(NMK)O(NMlog2K)O(NMlog2K)O(NM)去除冗余线性表*例2：最大奖品价值——小结去除冗余数据结构探索分析降低复杂度选取一个最合适的数据结构总结在算法设计和编程过程中，冗余的出现是难以避免的冗余是高效率的天敌，减少冗余，必然会使算法和程序效率提高很多去除冗余没有可套用的定理公式可用，只有认真分析、善于探索，并在做题中积累经验，才能得到去除冗余的好方法总结如果在做题时和做题后，思考一下，能否有更好的方法解决此题，此题还有冗余能去吗，必然会得到意想不到的收获。