动态规划-作业

1、例2：城市交通 有n个城市，编号1n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少？输入格式： 先输入一个n，表示城市数，n100。 下面的n行，是一个n*n的邻接矩阵map1.n,1.n。 mapi,j=0，表示城市i和城市j之间没有路相连，否则为两者之间的距离。输出格式： 一个数，表示从城市1走到城市n的最短距离。 输入数据保证可以从城市1走到城市n。动态规划的引入1输入样例： 110 5 3 0 0 0 0 0 0 0 05 0 0 1 6 3 0 0 0 0 03 0 0

2、 0 8 0 4 0 0 0 00 1 0 0 0 0 0 5 6 0 00 6 8 0 0 0 0 5 0 0 00 3 0 0 0 0 0 0 0 8 00 0 4 0 0 0 0 0 0 3 00 0 0 5 5 0 0 0 0 0 30 0 0 6 0 0 0 0 0 0 40 0 0 0 0 8 3 0 0 0 30 0 0 0 0 0 0 3 4 3 0动态规划的引入2动态规划简介 拦截导弹（NOIP1999）问题描述： 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度

3、。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格），计算这套系统最多能拦截多少导弹？如果要拦截所有导弹最少要配备多少套这种导弹拦截系统？样例输入： 8 389 207 155 300 299 170 158 65 样例输出： 6（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数）3例3、数塔问题问题描述设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 要求从根结点开始，请

4、找出一条路径，使路径之和最大，只要输出路径的和。输入数据：第一行为n(n100)，表示数塔的层数从第2行至n+1行，每行有若干个数据，表示数塔中的数值。输出数据：输出路径和最大的路径值。 4例4：跳马问题问题描述：马的路径问题，在一个n*m的棋盘上的P点有一个中国象棋的马，而另一个点Q为马的家，同时约定，Q在P的右边，如下图所示：试找出从P到Q的所有通路的条数。PQ穷举算法递归算法52007_2(普及组)（最短路线）某城市的街道是一个很规整的矩形网格（见下图），有7 条南北向的纵街，5 条东西向的横街。现要从西南角的A 走到东北角的B，最短的走法共有多少种？_. AB6 AB A点到B点的路径数量7例5：思考：求最长不下降序列问题描述：设有一个正整数的序列：b1,b2,bn，对于下标i1i2in，若有bi1bi2 bin，则称存在一个长度为l的不下降序列。如下列数列：13791638243718441921226315存在长度为5的不下降序列：1316384463存在长度8的不下降序列：7916181921226