资源描述：
《动态规划在信息学奥林匹克竞赛中应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、动态规划在信息学奥林匹克竞赛中的应用一.动态规划含义:在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果.因此,各个阶段决策确定后,组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程,就称为多阶段决策过程,这种问题称为多阶段决策问题.在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中
2、产生出来的,故有"动态"的含义,我们称这种解决多阶段决策最优化的过程为动态规划.二.动态规划特征动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段.动态规划一般还存在一条或多条状态转移方程.三.例题1.Catcher防卫导弹(GDOI'98)题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态规划算法中最基础的题目,用一个二维数组C[1..Max,1..2]来建立动态规划状态转移方程(注:C[1..Max,1]表示当前状态
3、最多可击落的导弹数,C[1..Max,2]表示当前状态的前继标志):Ci=Max{C[j]+1,(j=i+1..n)},然后程序也就不难实现了.示范程序:programcatcher_hh;varf:text;i,j,k,max,n,num:integer;a:array[1..4000]ofinteger;{导弹高度数组}c:array[1..4000,1..2]ofinteger;{动态规划数组}procedurereadfile;beginassign(f,'catcher.dat');reset(f);read
4、ln(f,num);fori:=1tonumdoreadln(f,a[i]);end;procedurework;beginfillchar(c,sizeof(c),0);c[num,1]:=1;{清空数组,赋初值}{开始进行动态规划}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;wri
5、teln;writeln('Max:',max);{打印最大值}max:=0;n:=0;fori:=1tonumdoifc[i,1]>maxthenbeginmax:=c[i,1];n:=i;end;{返回寻找路径}repeatwriteln(n,'');n:=c[n,2];untiln=0;end;beginreadfile;work;end.2.Perform巡回演出(GDKOI'2000)题目描述:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指
6、挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入:输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起
7、点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去.每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"375080"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI
8、,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.样例输入:362130150375080712011001001101
