ACM试题1168 圈圈

《ACM试题1168 圈圈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1168圈圈报告人：肖阳升问题描述1）将一个圆盘分成N（N<=6）个扇形，往每个扇形内放入一个整数（这些整数都要大于给定的K值）2）然后从这些整数中选择任意多个相邻的整数（可以选一个，也可以选多个），得到它们的和。问题描述3）将2）中所得的和排成从M开始的一组连续整数，M,M+1,…,J4）此题的任务是：往扇形中添加合适的整数，使得J值最大。示例N=6K=1M=3按此图放入整数时产生的序列为3,4,5,6,7,8,9,10,1110输入输出及数据规模输入：N,M,K(N<=6,M<=20,K<=20)输出：产生的序列M,M+1,…,J

2、中J的最大值，以及所有产生此类序列的整数放置方案，要求将最小的数作为每个方案中的第一个数，如：131025各个方案之间按升序排列分析采用深度优先搜索的方法得到所有可能的整数放置方案，然后逐一检查其所能得到的J（J的意义见前），最后得到J的最大值上边的算法效率太低，考虑缩小搜索范围算法设计用数组a来存放放置方案，显然有：K<=a[0]<=M;a[0]<=a[i]<=up;(up为a[i]的上界）易知J的最大可能值为M+N(N-2)+1Why?所以up=M+N(N-2)+1确定了上下界，搜索能在有限时间内结束算法设计（续）上一页的算法效率

3、太低，其时间代价为因此必须设法减小up的值如何减小上界先看一个例子：N=5,M=3,K=1;当前已经放好了0,1,2的位置，考虑在位置三放入整数的上界，易知3,5,7,8,12,15可由前三个整数生成，而4,6,9,10,11,13,14,16…均不可生成i01234a[i]357如何减小上界（续一）先定义一个概念对和式a[i]+…+a[j],当i<=b<=j或j

4、贡献的和式有4个当a[3]>11时，所有a[3]有贡献的和式都将大于11，所以仍然没有和式生成4,6,9,10,11，因此只能寄希望于a[4]放入a[4]后，a[4]有贡献而a[3]无贡献的和式只有4个，所以4,6,9,10,11中必然有一个无法生成如何减小上界（归纳）综上所述，减小a[pos]的上界主要在于计算：1）已经生成的和数与尚未生成的和数2）任意包含a[pos+1]~a[N-1]中的一个或多个且不包含a[pos]的和式的个数NUM然后从M开始的第NUM+1个尚未生成的和数就是a[pos]的上界ThankYou！