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

《国家集训队2004论文集 胡伟栋》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖南省长沙市长郡中学胡伟栋减少冗余与算法优化减少冗余与算法优化要提高算法的效率，必须减少算法中的冗余算法的目标：用最少的时间解决问题最高的效率冗余：多余的或重复的操作高效率在搜索、递推、动态规划……中，都可能出现冗余例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]表示

2、i拆分成若干个数，其中最大的数不超过2j的拆分方案数。递推方程：递推的表示：目标：最大数是最大数小于(初始值)例1：整数拆分——递推复杂度复杂度：时间复杂度：O(Nlog2N)空间复杂度：O(Nlog2N)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——递推中的冗余1=202=214=22C当j=M-k时，第j行要计算的点数为2k。例1：整数拆分——减少冗余当N=2M(M是非负整数)时

3、当i=x时，第i列要计算的点数与x的二进制表示中最末的0的个数相等12102112100210121102111210002时间复杂度：O(N)JI123012345678每列要计算的点是最下方连续的若干个点需要计算的点已知点不必求出的点JI123012345678例1：整数拆分——减少冗余当N=2M(M是非负整数)时在所有F[x,j](j一定,x为变量)中，只要存储x最大的一个即可。未知点处理中的点已知点不必求出的点空间复杂度：O(log2N)例1：整数拆分——减少冗余JI123012345678当N≠2M时，可转化成N=2M的形式求解例1：整数拆分——减少冗余设

4、N=2M-r(2M-1

5、从第i级走到第i+K级。例2：最大奖品价值——数学模型有一列数a0,a1,a2,…,aN,aN+1其中a0=0a1,a2,a3,…,aN>0aN+1=0从中选M+1个数…,，使1)0=i0

6、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]af1[b]时，f1[a]才

7、有用f2[j]f1[a1]f1[a2]f1[a3]……f1[ar]>>>>maxj-k≤a1