首 页科组简介下载中心文章中心客户留言论 坛博 客加入收藏
您当前的位置:惠州一中电教科组 -> 信息奥赛 -> 奥赛试题 -> 文章内容
 
栏目导航
热门文章
· 2007广东省普通高中..
· 2007广东省普通高中..
· [图文] 颠覆传统快捷..
· 第十一届全国青少年..
· 2006年广东省信息技..
· 2006年广东省信息技..
· 2006年广东省信息技..
· 2006年广东省信息技..
· [新闻] NOIP2006广东..
· [推荐] OIBH的NOIP模..
相关文章
noip2006提高组解题报告
作者:本站  来源:本站整理  发布时间:2007-5-16 20:41:56  发布人:yzriyang

减小字体 增大字体

题目一:energy

题目的意思是在这个环内选两个数合并成新的数,接着再继续合并,找到其合并的最大值,有可以理解为找一点断开,然后再进行合并,求其最大值,其算法为枚举+最小子母代价树(DP);其方程为:

F[I,J]=MAX{F[I,K]+F[K+1,J]+A[I]*A[K+1]*A[J+1]}(1<=I<=N,I<=J<=I+N,I<=K<=J)

F[I,I]:=0;

注意:1、求解时是将环线性化,所以要开到3*N的数组;

   2、枚举是枚举断开数字的位置;

 

题目二:budget

题目的方法是背包问题。但是要进行预处理,把所有的附件都组合在一起(因为附件最多只有两个,且附件没有在属于它的附件,所以最多只有四钟情况,主件,主件+附件1,主件+附件2,主件+附件1+附件2,即分解成几种物品)方程为:

F[I,J]:=MAX{F[K,J-PV[I]]+PW[I];F[K,J]}(1<=I<=MM,0<=J<=N,0<=K<=I-Q[I])

F[0,0]:=0;

注意:1、Q[I]是前一个主件到这个主件的相对距离(有附件的存在);

   2、PW[I]是第I个物品的价值,PV[I]是第I个物品的重量(要在前面求出来);

   3、MM是预处理之后的总件数;

   4、最后的答案要扫描一遍输出的,或是边动归边记录最大值;

 

题目三:jsp

题目算法简单:模拟法,扫描每个任务和该任务要在哪个机器上完工,然后再把这任务在该机器上的时间插入其时间空当(可用布尔数组代表这一时刻有没有机器在这里工作),最后输出这些机器完成所有任务的最后时间(最大值);建议多读几遍题,把重要内容标记好,会有好的收获的;

 

题目四:digital

数学题目,理解为从第二段开始使前面的数小于后一位的数,递推式为:

F[I,J]:=F[I-1,J+1]+F[I,J+1];

ANS:=ANS+F[I,J];

(2<=I<=(K-1) DIV R;1<=J<=2^R-1)

最后I=(K-1)DIV R+1时,1<=J<=2^(K-((K-1)DIV R)*R)-1

其式子可以从题目和样例推出来,至于精度方面:LONGINT 过五组数据INT64过七组数据 处理高精度全过(可以用LONGINT测试程序是否正确)

注意:数组可以开两个一维的高精数组,当前状况只与上一层状况有关,所以这样可以节省空间。

] [返回上一页] [打 印] [收 藏]
∷相关文章评论∷    (评论内容只代表网友观点,与本站立场无关!) [更多评论...]

 
关于本站 - 网站帮助 - 广告合作 - 下载声明 - 友情连接 - 网站地图 - 管理登录
Copyright © 2002-2006 dj.hzyz.net. All Rights Reserved .2006