《动态规划在信息学奥林匹克竞赛中的应用》由会员分享，可在线阅读，更多相关《动态规划在信息学奥林匹克竞赛中的应用（6页珍藏版）》请在金锄头文库上搜索。
1、动态规划在信息学奥林匹克竞赛中的应用一. 动态规划含义: 在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一 阶段都要做出决策,从而使整个过程达到最好的活动效果 .因此,各个阶段决策确定后,组成一个决策序列,因而 也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程 ,就称 为多阶段决策过程,这种问题称为多阶段决策问题.在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于当前状态,又随即引 起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有动态的含义,我们称这种解决多阶段决策 最优化
2、的过程为动态规划.二. 动态规划特征 动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段. 动态规划一般还存在一条或多条状态转移方程.三. 例题1. Catcher 防卫导弹 (GDOI98) 题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列 这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态规划算法中最基础 的题目,用一个二维数组Cl.Max,1.2来建立动态规划状态转移方程(注:Cl.Max,l表示当前状态最多可击落 的导弹数,C1.Max,2 表示当前状态的前继标志):Ci=MaxCj+1,(j=i+1.n),然后程序也就不难实现了.示
3、范程序:program catcher_hh;varf:text;i,j,k,max,n,num:integer;a:array1.4000of integer; 导弹高度数组c:array1.4000,1.2of integer; 动态规划数组procedure readfile;beginassign(f,catcher.dat); reset(f); readln(f,num);for i:=1 to num doreadln(f,ai);end;procedure work;beginfillchar(c,sizeof(c),0); cnum,1:=1;清空数组,赋初值开始进行动态规划
4、for i:=num-1 downto 1 dobeginn:=0;max:=1;for j:=i+1 to num doif (aiaj) and (maxmax then beginmax:=ci,1;n:=i;end;返回寻找路径repeatwriteln(n, ); n:=cn,2; until n=0;end;beginreadfile; work;end.2. Perform 巡回演出 (GDKOI2000)题目描述:Flute 市的 Phlharmoniker 乐团 2000 年准备到 Harp 市做一次大型演出,本着普及古典音乐的目的,乐团 指挥L.Y.M准备在到达Harp市之
5、前先在周围一些小城市作一段时间的巡回演出，此后的几天里,音乐家们将每 天搭乘一个航班从一个城市飞到另一个城市，最后才到达目的地Harp市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班 表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入:输入文件包括若干个场景每个场景的描述由一对整数n(2v=nv=10)和k(lv=kv=1000)开始，音乐家们 要在这n个城市作巡回演出,城市用1.n标号，其中1是起点Flute市,n是终点Harp市，接下来有n*(n-1)份航班 表，一份航班表一行,描述每对城市之间的航线
6、和价格,第一组n-1份航班表对应从城市1到其他城市(2,3，.n)的 航班,接下的n-1行是从城市2到其他城市(1,3,4.n)的航班，如此下去.每份航班又一个整数d(1v=dv=30)开始，表示航班表循环的周期，接下来的d个非负整数表示1,2.d天 对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如3 75 0 80表示第一天 机票价格是75KOI,第二天没有航班，第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班，如 此循环.输入文件由 n=k=0 的场景结束.输出 :对每个场景如果乐团可能从城市1出发，每天都要飞往另一个城市，最后(经过k天)抵达
7、城市n,则输出 这k个航班价格之和的最小值如果不可能存在这样的巡回演出路线，输出0.样例输入:36213015037508071201100100 110 120 04607060503013514027080232 0 701 8000样例输出:4600初看这道题，很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关，符合动 态规划的无后效性原则，即只与上一个状态相关联，而某一天x航班价格不难求出S=C(x-1) mod m +1. 我们用天数和地点来规划用一个数组A1.1000,1.10来存储,Ai,j表示第i天到达第j个城市的最优值,Ci,j,l 表示i城市与j城市
8、间第1天航班价格，则Ai,j=MinAi-1,l+Cl,j,i(l=1.n且Cl,j,iv0),动态规划方程一出,尽可以放怀大笑了.示范程序:program perform_hh; varf,fout:text;p,1,i,j,n,k:integer;a:arrayc:array1.1000,1.10of integer;动态规划数组1.10,1.10of record 航班价格数组num:integer;t:array1.30of integer;end;1.1000 of integer; work;e:array procedure begin人工赋第一天各城市最优值 for i:=1
9、to n do beginif c1,i.t10then a1,i:=c1,i.t1; end;for i:=2 to begindoforj:=1ton dobeginfor1:=1ton dobeginif (j1)and(c1,j.t(i-1)mod c1,j.num+10)判断存在航班and(ai,j=0)or (ai-1,1+c1,j.t(i-1) mod c1,j.num+1ai,j)thenai,j:=ai-1,1+c1,j.t(i-1) mod c1,j.num+1;赋值end;end; 判断比当前解优end;ep:=ak,n; 第 p 个场景的最优值end;procedure
10、 readfile;读文件beginassign(f,PERFORM.DAT); reset(f); assign(fout,PERFORM.OUT); rewrite(fout); readln(f,n,k); p:=0;while (n0) and (k0) do beginp:=p+1;fillchar(c,sizeof(c),0);fillchar(a,sizeof(a),0);for i:=1 to n do beginfor j:=1 to i-1 do beginread(f,ci,j.num);for l:=1 to ci,j.num do read(f,ci,j.tl);en
11、d;for j:=i+1 to n do beginread(f,ci,j.num);for l:=1 to ci,j.num do read(f,ci,j.tl);end;end;work;readln(f,n,k);end;输出各个场景的解for i:=1 to p-1 do writeln(fout,ei); write(fout,ep);close(f); close(fout);end;beginreadfile;end.四. 小结动态规划与穷举法相比,大大减少了计算量,丰富了计算结果,不仅求出了当前状态到目标状态的最优 值,而且同时求出了到中间状态的最优值,这对于很多实际问题来说是
12、很有用的.这几年,动态规划已在各省市信 息学奥林匹克竞赛中占据相当重要的地位,每年省赛8道题目中一般有23道题目属于动态规划,动态规划相比 一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法!五. 课后题目1. m个人抄n本书，每本书页数已知,每个人（第一个人除外）都必须从上一个人抄的最后一本书的下一本抄起（书必须整本整本的抄）,求一种分配方法,使抄书页数最多的人抄书页数尽可能少.（GDOI99 Books）.2. 有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编码长度最短。（GDKOI2000Compress）3. Canada境
13、内有自西向东的一系列城市：Halifax,Hamilton,Montelia,Vancouver.,各个城市之间可能有航 班相连，也可能没有，现要求从最西的城市出发，自西向东到达最东的城市，再返回最西的城市，除最西城 市外，其他每个城市只能访问一次，求最多能访问多少个城市动态规划-航线设置问题描述:美丽的莱茵河畔,每边都分布着 N 个城市,两边的城市都是唯一对应的友好城市,现需要在友好城 市开通航线以加强往来.但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象.现在 要求近可能多地开通航线并且使航线不能相交!假如你是一个才华横溢的设计师,该如何设置友好城市间的航线使的航线数又最大又不相交呢?分析:此问题可以演化成求最大不下降序列来完成.源程序如下:program dongtai; 动态规划之友好城市航线设置问题vard:array1.1000,1.4 of integer;i,j,k,n,L,p:integer;procedure print（L:integer）; 打印结果beginwriteLn（最多可设置的航线数是：,k）;repeatwrite
