动态规划题目选讲.

动态规划题目选讲江苏省淮阴中学张坤动态规划无后效性、最优子结构优化：时间复杂度、空间复杂度、编程复杂度空间复杂度的优化一般用滚动数组即可对于初等的dp优化，其对编程复杂度影响不大。有一些单调性优化，需要用到平衡树、凸包等知识，NOIP不作要求。动态规划无后效性、最优子结构优化：时间复杂度、空间复杂度、编程复杂度空间复杂度的优化一般用滚动数组即可对于初等的dp优化，其对编程复杂度影响不大。有一些单调性优化，需要用到平衡树、凸包等知识，NOIP不作要求。•线性动态规划•区间动态规划•状态压缩动态规划•树形动态规划动态规划的分类动态规划性质：无后效性、最优子结构优化方向：时间复杂度、空间复杂度、编程复杂度优化方法：空间复杂度用滚动数组单调性优化，队列、平衡树、平行四边形法则、凸包。题目选讲例题一：关灯问题在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉，就会每秒造成一定的损失。小朋友一开始在某一个位置，在他左边和右边分别有一些灯，给出这些灯和他的距离以及每个灯每秒会造成的损失，求一个方案使得损失最小，输出最小损失。灯的个数=1000一些想法•关掉的灯一定是一个连续的区间•如果路过一个灯但是没有去关掉它……解决方案•设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本身）的加分计算方法如下：例题二：加分二叉树•左子树的加分×右子树的加分＋本身的分数•若某个子树为主，规定其加分为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,1到m,n一条从m,n到1,1),并且路径之上的权值之和最大例题三：传纸条•30%的数据满足：1=m,n=10•100%的数据满足：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]+a[k][l].•注意判断是否相交！方程•纸条传的横坐标+纵坐标=走的步数•消维！时间！33039285570以斜列即横坐标和纵坐标之和作为一维其他表示方式例题四•题目描述：•要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod1000000007后的答案。例题四•输入描述：•共有T组数据。•对于每组数据，第一行为一个整数n，表示有n个班级。•2~n+1行，每行有最多100个数字，表示第i-1班待选班服的编号。•输出描述：•对于每组数据，输出方案总数mod1000000007后的答案。•样例输入：•2•3•51001•2•5100•2•35•8100•样例输出：•4•4例题四•对于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[i][j]+=f[i-1][j-(1(k-1))]例题五：•在W星球上有n个国家。为了各自国家的经济发展，他们决定在各个国家•之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿•意修建恰好n–1条双向道路。每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有2个、4个国家，如果该道路长度为1，则费用为1×|2–4|=2。图中圆圈里的数字表示国家的编号。例题五：•由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建•费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计•算出所需要的费用。请你帮助国王们设计一个这样的软件。例题五：•Input•输入的第一行包含一个整数n，表示W星球上的国家的数量，国家从1到n•编号。接下来n–1行描述道路建设情况，其中第i行包含三个整数ai、bi和ci，表•示第i条双向道路修建在ai与bi两个国家之间，长度为ci。•Output•输出一个整数，表示修建所有道路所需要的总费用。例题五：•树形DP记录size。然后每个子树回来是边的两边数量是size子节点和n−size子节点。例题六：例题六：例题六：例题六•10%的数据中，n≤1000,K=1；•30%的数据中，K=1；•80%的数据中，每个村庄相邻的村庄数不超过25；•90%的数据中，每个村庄相邻的村庄数不超过150；•100%的数据中，3≤n≤100,000,1≤K≤2。思考例题六•对于k=0的情况：•我们发现遍历一棵树最后回到原点，那么对于所有的边，我们都是走过去，再走回来。•答案(n-1)*2例题六•对于k=1的情况•设每条边长度为1，然后树上找最长链，然后这条链走过去就不再一步步往回了，直接从链底连一条边去链顶，然后链中间连的那些点，直接走过去再走回来，它们那些边的答案是不变的。•答案(n−1)*2−(最长链长度)+1•可以证明不能减得更多啦。例题六•对于k=2的情况•设上一次的直径上的边的边长都为-1，因为再走一次会坑，然后树上找最长链。•答案(n−1)*2−(链1长度)+1−(链2长度)+1•可以证明不能减得更多啦。•题意：有n个星球，其中有些星球上有多个工作，有些星球上有些资源（但是一个星球上的资源只能提供给一个工厂），知道在一些星球边建立边（双向边）的代价，问使得得到资源的工厂的数目最多的多少，在些前提下代价最小是多少。•资源和含有工厂的星球个数都不超过4•n≤200例题七：暴力枚举匹配方案，求最短路？想法暴力枚举匹配方案，求最短路？两条路径公用边怎么办？想法•特殊的星球数量很少，可以枚举状态28=256思考•特殊的星球数量很少，可以枚举状态28=256•如何表示状态?思考•设F[i][s]表示现在路径包含第i个星球，已经连接上的特殊星球选择方案是s的最少代价。•如何转移？•设F[i][s]表示现在路径包含第i个星球，已经连接上的特殊星球选择方案是s的最少代价。•如何转移？•s从00000000到11111111•s相同F[i][s]从代价小的转移到代价大的•如何转移？•s相同F[i][s]从代价小的转移到代价大的•spfa！•难点：•对于s的合并操作，枚举！voidSpfa(ints,intk){intu,v,d,t;for(inttop=1;top=bot;top++){u=Q[top];for(intj=E[u].size()-1;j=0;j--){v=E[u][j];d=D[u][j];t=s|S[v];if(F[u][s]+d*kF[v][t]){F[v][t]=F[u][s]+d*k;if(t==s&&V[v][s]){V[v][s]=false;Q[++bot]=v;}}}V[u][s]=true;}}voidDP(){inttmp,k;for(ints=1;s=ALL;s++){k=0;for(inti=0;iK;i++)if(s&(1i))k++;for(inti=K;i2*K;i++)if(s&(1i))k--;k=k!=0?1:0;bot=0;for(inti=1;i=n;i++){if(S[i]&&(S[i]&s)==0)continue;for(intk=(s-1)&s;k;k=(k-1)&s)F[i][s]=min(F[i][s],F[i][k|S[i]]+F[i][(s^k)|S[i]]);V[i][s]=false;Q[++bot]=i;}Spfa(s,k);}}谢谢！