TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3317
  • 题目
  • P3317【APIO2015】巴厘岛的雕塑
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,64m
    问题描述

        印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
        在这条主干道上一共有N座雕塑,为方便起见,我们把这些从1到N连续地进行标号,其中第i座雕塑的年龄是Yi年。为了使这条路的环境更加优美,政府想把这些雕塑分成若干组,并通过在组与之间种上一些树,来吸引更多的游客来巴厘岛。
        下面是将雕塑分组的规则:
        这些雕塑必须被分为恰好X组,其中A≤X≤B,每组必须含有至少一个雕塑,每个雕塑也必须属于且只一组。同一组中的所有雕塑必须 位于这条路的连续一段上。
        当雕塑被分好组后,对于每个组,我们首先计算出该组所有雕塑的年龄和,然后计算将每组年龄和按位取或(即对上述年龄和按位取或),我们把按位取或后得到的结果称为这一分组的最终优美度(颜值)。
        请问政府能得到的最小终优美度(颜值)是多少?
        备注:
        将两个非负数P和Q按位取或是这样进行计算的:
        首先把P和Q转换成二进制:设nP是P的二进制位数,nQ是Q的二进制位数,M为nP和nQ中的最大值。P的二进制表示为pM-1,pM-2,…,p1,p0,Q的二进制表示为qM-1,qM-2,…,q1,q0,其中pi和qi分别是P和Q二进制表示下的第i位,第M-1位是数的最高位,第0位是数的最低位。
    P与Q按位取或后的结果是:(pM-1或qM-1)(pM-2或qM-2)…(p1或q1)(p0或q0)。其中 :
        0 或 0 = 0
        0 或 1 = 1
        1 或 0 = 1
        1 或 1 = 1

    输入格式

        输入的第一行包含三个用空格分开的整数N,A和B。
        第二行包含N个用空格分开的整数Y1,Y2,...,YN。

    输出格式

        输出一行一个数,表示最小的最终优美度。

    样例输入

    6 1 3
    8 1 2 1 5 4

    样例输出

    11

    提示

    提示

        将这些雕塑分为2组,(8,1,2)和(1,5,4),它们的和是(11)和(10),最终优美是(11或10)=11。(不难验证,这也是最终优美度的最小值。)
    数据规模和约定
        共有五部分数据(或称5个子任务)。
        第1部分数据占9分,数据范围满足:1≤N≤20,1≤A≤B≤N,0≤Yi≤1,000,000,000;
        第2部分数据占16分,数据范围满足:1≤N≤20,1≤A≤B≤min(20,N),0≤Yi≤10;
        第3部分数据占21分,数据范围满足:1≤N≤100,A=1,1≤B≤min(20,N),0≤Yi≤20;
        第4部分数据占25分,数据范围满足:1≤N≤100,1≤A≤B≤N,0≤Yi≤1,000,000,000;
        第5部分数据占29分,数据范围满足:1≤N≤2000,A=1,1≤B≤N,0≤Yi≤1,000,000,000。