资源描述：
《动态规划题目选讲ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划题目选讲江苏省淮阴中学张坤线性动态规划区间动态规划状态压缩动态规划树形动态规划动态规划的分类性质：无后效性、最优子结构优化方向：时间复杂度、空间复杂度、编程复杂度优化方法：空间复杂度用滚动数组单调性优化，队列、平衡树、平行四边形法则、凸包。题目选讲例题一：关灯问题在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉，就会每秒造成一定的损失。小朋友一开始在某一个位置，在他左边和右边分别有一些灯，给出这些灯和他的距离以及每个灯每秒会造成的损失，求一个方案使得损失最小，输出最小损失。灯的个数<=1000一些想法关掉的灯一定是一个连续的区间如果路过一
2、个灯但是没有去关掉它……解决方案设Left[i][j]，Right[i][j]表示区间[i,j]中的灯都被关掉之后的最小损失，Left的位置在i，Right的位置在j转移：考虑当前的关灯操作Left/Right[i][j-1],Left/Right[i+1][j]->Left/Right[i][j]时间复杂度：O(N^2)设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树(也包含tree本身）的加分
3、计算方法如下：例题二：加分二叉树左子树的加分×右子树的加分＋本身的分数若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。注意到一棵子树的中序遍历是一段连续的区间思考转移方程枚举区间中的的根设F[i][j]表示中序遍历为[i,j]这个区间的子树的最大分数，Score[i]表示第i个点的分数F[i][j]=max(F[i][k-1]*F[k+1][j]+Score[k])注意i≤k-1，k+1≤j题目描述：在一个矩阵内找出两条从1,1到m,n的路径(一条从1,
4、1到m,n一条从m,n到1,1),并且路径之上的权值之和最大例题三：传纸条30%的数据满足：1<=m,n<=10100%的数据满足：1<=m,n<=50如何表示当前状态？如何确保路径不重复？思考如何表示当前状态？横坐标与纵坐标之和相等如何确保路径不重复？当前不重复，之后不相交思考设F[i][j][k][l]为一张纸条传到i,j另一张传到k,l时路径上权值和的最大值。F[i][j][k][l]=max{F[i-1][j][k-1][l],F[i-1][j][k][l-1],F[i][j-1][k-1][l],F[i][j-1][k][l-1]}+a[i][j]
5、+a[k][l].注意判断是否相交！方程纸条传的横坐标+纵坐标=走的步数消维！时间！33039285570以斜列即横坐标和纵坐标之和作为一维其他表示方式例题四题目描述：要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod1000000007后的答案。例题四输入描述：共有T组数据。对于每组数据，第一行为一个整数n，表示有n个班级。2~n+1
6、行，每行有最多100个数字，表示第i-1班待选班服的编号。输出描述：对于每组数据，输出方案总数mod1000000007后的答案。样例输入：2351001251002358100样例输出：44例题四对于30%的数据，1<=T<=3,1<=n<=3，每班待选样式不超过10种。对于50%的数据，1<=T<=5,1<=n<=5，每班待选样式不超过50种。对于100%的数据，1<=T<=10,1<=n<=10，每班待选样式不超过100种。思考例题四f[i][j]表示前i件衣服达到j状态的方案那么显然f[i][j]+=f[i-1][j]若班级k可以穿i这件衣服，则f[
7、i][j]+=f[i-1][j-(1<<(k-1))]例题五：在W星球上有n个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好n–1条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有2个、4个国家，如果该道路长度为1，则费用为1×
8、2–4
9、=2。图中圆圈里的数字表示国家的编号。例题五：由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建费用难以用人工计算，国王们决定找人设计一个
10、软件，对于给定的建造方案，计算出所需要的费用。请你帮
