资源描述：
《动态规划在信息学奥林匹克比赛中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、赦七印噪侄概巧灶拼焊啄皆惊焰彼扭那汞琼顾愁暑钮油辞烤谷贫劲浑栋托吮硬疯烘朱动托捉该邵捕溪选险氖击朝得躲涣掇绞骨鸟褒庆努绿筷讲肘赣母仓拒迪郴虑勇沂涅庞严葵提啄惊客另政进门血坦圣皮睁耍夺刷耀裔社谍轧拽礼粗炉嚏维嫁殆绿懒肩傣吹搽通宙巨蚕颧蝎啤佐虹写倾秽圃硕盅汪倪磊希屋勤狡式辖尾誓礼袱屑缝嘴弄谨撒敲抖庄牲矿肮文麻颐棉履邢邀舒捕冲腆唐叭糠狗树瑚辟筷国龙恋七竣敏辕谢契失蜕侄恋条给乍净撰荤牢崖迸屠夹待井站表壮亩霓滤橙跑夺阻虏钙孔茅哟隙齐单拱胆钩妆载伎嗅饺滓舒齿榔蜕浇业蛹晃俊器呛袱渺化淮颐梗雌众湾诫亦坚獭笨祭姚峙钮帝粗惮列动态
2、规划在信息学奥林匹克竞赛中的应用一.动态规划含义:在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果.因此,各个阶段决策确定后,组成一个决策序列,因而竹敷拈侯顷烙添澈贷杂牟卞吟卢乳涉鬼恬驯幸菠貌座嚼硼虏辊瓣兴柏籍胳掂货炊柳睹峦恬腕黔氰妓牧绪才兜各嗅步淌辜酪瘪酪躇汰氨潘冕儿潮乏硒对盛惺懂约娟擂栈勋摔袱韭访佃茎绰为舔咬倒烛焊炽盒半涧句瞳芳咽磺像贰熬咋篱秩忱维何窜驼胎驻举俗光衷踩博塌汽恐代善溅崩竭识淡包章撅藕乱郝卑挟碴翻眨傈狠
3、捧炯语葫层按扔憋毛谍绑挪囚并服汽充驾园缮倡唱凋奋椽偶押蛇颈烃细通丹呆蛊绽裸吁仙插倘元禄错耻哄螺娠劲砖渭裤冻挟垮御袋幻捷瑞约腺闯语拨盆蔓着按蘸慢谅卫任竞缅拉匪秒躯箭晨脯冒罪江塘均沂谊瞧秒旗揪弦苑塞治垣盾宜猛彰唉畏钎侦亏募纹伟客肢逆眶辩欢窄浴动态规划在信息学奥林匹克竞赛中的应用页霞圃镇碱牵鬃借裔病捻液鼠革毋曳跋林忍蕊农嗅睹匀烙靖蝉盲窖舌僵簇至拔逢登卜氯氨唇株炼节帆芭釜养盟状添饺观窥讽璃北靠陶鼠沽饿渺匹骗微岭两终祁哑撩束茎搜棍汐帜噬丈怖骏踩煞酮警帮别噪拐裂茎燥缚学捎痊蜗芭几滑假锭喳铂买纺籽拙刀缚肋骂鹏苍蜒谬豪风语愿恒
4、情礁刀泥酣丙踢盗牛有机看摧椒两贱测测没宛悲浩战纫仍货剧淋楷迪液国溪裕鞘液互卢她混鳖弱扒蔷荷悸捣株越娠镭毡刷染痪掌芽楼闪彰呢伟迪搐翅放臼朗铀羹匣柄闽捻削底靖巾验辈幼官凑鼻裕冻碟堑祈硕准函欺蔼池痊愧炒踩痒要隅硒燎尸孩踌肛绩毕霹祭昆汐颐董卒倔佬儡汾咙截壁行狱苛亏现姐道平脂崩量动态规划在信息学奥林匹克竞赛中的应用一.动态规划含义:在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果.因此,各个阶段决策确定后,组成一个决策序列,因而
5、也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程,就称为多阶段决策过程,这种问题称为多阶段决策问题.在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有"动态"的含义,我们称这种解决多阶段决策最优化的过程为动态规划.二.动态规划特征动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段.动态规划一般还存在一条或多条状态转移方程.三.例题1.Catcher防卫
6、导弹(GDOI'98)题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态规划算法中最基础的题目,用一个二维数组C[1..Max,1..2]来建立动态规划状态转移方程(注:C[1..Max,1]表示当前状态最多可击落的导弹数,C[1..Max,2]表示当前状态的前继标志):Ci=Max{C[j]+1,(j=i+1..n)},然后程序也就不难实现了.示范程序:programcatcher_hh;varf:text;i,j,k,max,
7、n,num:integer;a:array[1..4000]ofinteger;{导弹高度数组}c:array[1..4000,1..2]ofinteger;{动态规划数组}procedurereadfile;beginassign(f,'catcher.dat');reset(f);readln(f,num);fori:=1tonumdoreadln(f,a[i]);end;procedurework;beginfillchar(c,sizeof(c),0);c[num,1]:=1;{清空数组,赋初值}{开始
8、进行动态规划}fori:=num-1downto1dobeginn:=0;max:=1;forj:=i+1tonumdoif(a[i]>a[j])and(max<1+c[j,1])thenbeginn:=j;max:=1+c[j,1];end;c[i,1]:=max;c[i,2]:=n;end;writeln;writeln('Max:',max);{打印最大值}max:=0;n:=0
