|
|
|
|
动态规划在信息学奥林匹克竞赛中的应用(二) |
2. Perform巡回演出 (GDKOI'2000)
题目描述:
Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).
由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.
输入:
输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点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天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.
输出:
对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.
样例输入:
3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0
样例输出:
460
0
初看这道题,很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班价格不难求出S=C[(x-1) mod m +1].我们用天数和地点来规划用一个数组A[1..1000,1..10]来存储,A[i,j]表示第i天到达第j个城市的最优值,C[i,j,l]表示i城市与j城市间第l天航班价格,则A[i,j]=Min{A[i-1,l]+C[l,j,i] (l=1..n且C[l,j,i]<>0)},动态规划方程一出,尽可以放怀大笑了.
示范程序:
四.小结
动态规划与穷举法相比,大大减少了计算量,丰富了计算结果,不仅求出了当前状态到目标状态的最优值,而且同时求出了到中间状态的最优值,这对于很多实际问题来说是很有用的.这几年,动态规划已在各省市信息学奥林匹克竞赛中占据相当重要的地位,每年省赛8道题目中一般有2~3道题目属于动态规划,动态规划相比一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法!
五.课后题目
1. m个人抄n本书,每本书页数已知,每个人(第一个人除外)都必须从上一个人抄的最后一本书的下一本抄起(书必须整本整本的抄),求一种分配方法,使抄书页数最多的人抄书页数尽可能少. (GDOI''99 Books).
2. 有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编码长度最短。 （GDKOI'2000 Compress)
3. Canada境内有自西向东的一系列城市：Halifax,Hamilton,Montelia,Vancouver...，各个城市之间可能有航班相连，也可能没有，现要求从最西的城市出发，自西向东到达最东的城市，再返回最西的城市，除最西城市外，其他每个城市只能访问一次，求最多能访问多少个城市．
|
|
|
