noip2006 提高组 复赛试题

《noip2006 提高组 复赛试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国信息学奥林匹克联赛（NOIP2006）复赛提高组全国信息学奥林匹克联赛（NOIP2006）复赛提高组（请选手务必仔细阅读本页内容）一、题目概况中文题目名称能量项链金明的预算方案作业调度方案2k进制数英文题目名称energybudgetjspdigital可执行文件名energybudgetjspdigital输入文件名energy.inbudget.injsp.indigital.in输出文件名energy.outbudget.outjsp.outdigital.out每个测试点时限1秒1秒1秒1秒测试点数目10101010每个测试点分值10101010比较方式全文比较

2、全文比较全文比较全文比较题目类型传统传统传统传统二、提交源程序文件名对于Pascal语言energy.pasbudget.pasjsp.pastwostack.pas对于C语言energy.cbudget.cjsp.ctwostack.c对于C++语言energy.cppbudget.cppjsp.cpptwostack.cpp三、编译命令（不包含任何优化开关）对于Pascal语言fpcenergy.pasfpcbudget.pasfpcjsp.pasfpcdigital.pas对于C语言gcc–oenergygcc–obudgetgcc–ojspgcc–odigitale

3、nergy.cbudget.cjsp.cdigital.c对于C++语言g++-oenergyg++-obudgetg++-ojspg++-odigitalenergy.cppbudget.cppjsp.cppdigital.cpp四、运行内存限制运行内存上限128M128M128M128M注意事项：1.文件名（程序名和输入输出文件名）必须使用大写。2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3.全国统一评测时采用的机器配置为：CPU1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。第1页总6

4、页全国信息学奥林匹克联赛（NOIP2006）复赛提高组1．能量项链(energy.pas/c/cpp)【问题描述】在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn（Mars单

5、位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*

6、3*5+10*5*10=710。【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i

7、能量。【输入输出样例】energy.inenergy.out471023510第2页总6页全国信息学奥林匹克联赛（NOIP2006）复赛提高组2．金明的预算方案(budget.pas/c/cpp)【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件