动态规划的模型构建分析报告.ppt

(1*21+2*21)+(2*22+3*22)+(3*23+4*23)=82 =(1*21+2*22+3*23)+(2*21 +3*22+4*23)=82 输入数据： 第一行:宽度W（1~99奇数）和高度H（1 ~ 100整数） 接下来给出了一块馅饼信息。由4个正整数组成，分别表示了馅饼的 初始下落时刻、水平位置、下落速度、分值。 游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。 输出数据： 收集到的馅饼最大分数之和。 由上图可知，尽管下落了4个馅饼，但只能接到3个： 第1时刻可以接到分值为5的馅饼 第2时刻可以接到分值为3的馅饼 第3时刻可以接到分值为4的馅饼 因此馅饼的总分值为5+3+4=12 分析 由于馅饼下落的时间和速度都不同，人只能向左右移动，馅饼只能向下移动。人和馅饼都同时移动，思考起来比较复杂，因此我们需要转变思路： 算出每个时刻落到最底层的每个格子有多少分值的馅饼。 如果将馅饼当成参照物，则馅饼向下落，可以看成馅饼不动，人往上走去摘取馅饼，这样人每1时刻都可以走到上一行的5个格子，如右图： 动态规划 计算出每个格子每个时刻可能达到的馅饼分值，填入W*H的天幕表。 其中C[i,j]表示天幕的第i行第j列的馅饼分值，即第i时刻，馅饼落到最底行的馅饼分值。 设F(i,j)表示人走到第i行j列所取得的馅饼最大分值和，则有， 0=i=T,1=j=W,决策数为5个 时间复杂度为O(5WT) 问题6：加分二叉树 给定一个中序遍历为1,2,3,…,n的二叉树 每个结点有一个权值 定义二叉树的加分规则为： 左子树的加分× 右子树的加分＋根的分数 若某个树缺少左子树或右子树，规定缺少的子树加分为1。 构造符合条件的二叉树 该树加分最大 输出其前序遍历序列 样例 中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145. 分析 性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！ 因此，假设二叉树的根结点为k，那么中序遍历为1,2,…,n的遍历序列，左孩子序列为1,2,…,k-1，右孩子序列为k+1,k+2,…,n，如下图 动态规划 设f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分，则有： f(i,j)=max{f[i,k-1]*f[k+1,j] +d[k]} 显然 f(i,i)=d[i] 答案为f(1,n) 1=i=k==j=n 时间复杂度 O(n3) 要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为i,i+1,…,j的二叉树的取最优决策时的根结点为k 最后前序遍历这个树即可。 思考题：选课 大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。 每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，《数据结构》必须在选修了《高级语言程序设计》之后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，……。 每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。 输入 输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学生可以选的课程总数（1≤N≤M)。 以下M行每行代表一门课，课号依次为1，2……M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。 输出 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。 问题7：聚会的快乐 你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人(姓名，他幽默的系数，以及他上司的名字)，编程找到能使幽默系数和最大的若干个人。 【输入】 第一行一个整数N(N100)。接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，幽默系数是在0到100之间的整数。 【输出】 所邀请的人最大的幽默系数和。 样例 【样例】 party.in par